Submission #11,022

2024-06-13 06:57:00

cpp17

Accepted 100/100

1.05s

612 KiB

#include "KutyakMacskak.h"

#include <vector>
#include <algorithm>
#include <numeric>
#include <deque>

using namespace std;

void insertion_sort(vector<int>& group, int dog) {
    auto cmp = [dog](int c1, int c2) -> bool {
        return ask(dog, c1, c2) == c1 ? true : false;
    };
    for (int i=1; i<(int)group.size(); ++i) {
        int lo = -1, hi = i;
        while (lo+1 < hi) {
            int mid = (lo+hi)/2;
            if (!cmp(group[mid], group[i]))
                hi = mid;
            else
                lo = mid;
        }
        for (int j=i; j>hi; --j)
            swap(group[j-1], group[j]);
    }
}
vector<int> find_order(int N, int M) {
    vector<int> cats(M);
    iota(cats.begin(), cats.end(), 1);
    insertion_sort(cats, 1);
    int nearcat = cats[0], farcat = cats[M-1];
    int X = 2;
    while (ask(X, nearcat, farcat) == nearcat)
        ++X;
    vector<bool> is_opposite(M, false);
    for (int j = 1; j+1 < M; ++j) {
        int cat = cats[j];
        if (ask(X, cat, nearcat) == nearcat)
            is_opposite[j] = true;
    }
    deque<int> ord({cats[0]});
    for (int j=1; j<M; ++j) {
        if (is_opposite[j])
            ord.push_front(cats[j]);
        else
            ord.push_back(cats[j]);
    }
    return vector<int>(ord.begin(), ord.end());
}

Subtask		Sum	Test	Verdict	Time	Memory
	subtask1	0/0
			1	Accepted	3ms	356 KiB
			2	Accepted	908ms	612 KiB
	subtask2	6/6
			3	Accepted	984ms	424 KiB
			4	Accepted	985ms	504 KiB
			5	Accepted	1.001s	360 KiB
			6	Accepted	972ms	508 KiB
			7	Accepted	961ms	484 KiB
	subtask3	7/7
			8	Accepted	4ms	436 KiB
			9	Accepted	4ms	548 KiB
			10	Accepted	3ms	408 KiB
			11	Accepted	4ms	504 KiB
			12	Accepted	4ms	396 KiB
			13	Accepted	28ms	384 KiB
			14	Accepted	35ms	384 KiB
	subtask4	10/10
			15	Accepted	8ms	356 KiB
			16	Accepted	8ms	384 KiB
			17	Accepted	8ms	356 KiB
			18	Accepted	9ms	396 KiB
			19	Accepted	8ms	228 KiB
			20	Accepted	9ms	396 KiB
			21	Accepted	8ms	300 KiB
			22	Accepted	9ms	256 KiB
			23	Accepted	10ms	300 KiB
			24	Accepted	12ms	360 KiB
			25	Accepted	12ms	384 KiB
			26	Accepted	12ms	360 KiB
			27	Accepted	9ms	512 KiB
			28	Accepted	8ms	256 KiB
			29	Accepted	10ms	416 KiB
	subtask5	12/12
			30	Accepted	8ms	356 KiB
			31	Accepted	8ms	384 KiB
			32	Accepted	8ms	356 KiB
			33	Accepted	9ms	396 KiB
			34	Accepted	8ms	228 KiB
			35	Accepted	9ms	396 KiB
			36	Accepted	8ms	300 KiB
			37	Accepted	9ms	256 KiB
			38	Accepted	10ms	300 KiB
			39	Accepted	12ms	360 KiB
			40	Accepted	12ms	384 KiB
			41	Accepted	12ms	360 KiB
			42	Accepted	9ms	512 KiB
			43	Accepted	8ms	256 KiB
			44	Accepted	10ms	416 KiB
			45	Accepted	43ms	316 KiB
			46	Accepted	32ms	492 KiB
			47	Accepted	43ms	420 KiB
			48	Accepted	37ms	420 KiB
			49	Accepted	50ms	536 KiB
			50	Accepted	41ms	424 KiB
			51	Accepted	41ms	384 KiB
			52	Accepted	45ms	528 KiB
			53	Accepted	45ms	356 KiB
			54	Accepted	54ms	420 KiB
			55	Accepted	57ms	360 KiB
			56	Accepted	46ms	532 KiB
			57	Accepted	46ms	492 KiB
			58	Accepted	46ms	384 KiB
			59	Accepted	50ms	384 KiB
	subtask6	65/65
			60	Accepted	3ms	376 KiB
			61	Accepted	977ms	428 KiB
			62	Accepted	984ms	424 KiB
			63	Accepted	985ms	504 KiB
			64	Accepted	1.001s	360 KiB
			65	Accepted	972ms	508 KiB
			66	Accepted	961ms	484 KiB
			67	Accepted	4ms	436 KiB
			68	Accepted	4ms	548 KiB
			69	Accepted	3ms	408 KiB
			70	Accepted	4ms	504 KiB
			71	Accepted	4ms	396 KiB
			72	Accepted	28ms	384 KiB
			73	Accepted	35ms	384 KiB
			74	Accepted	8ms	356 KiB
			75	Accepted	8ms	384 KiB
			76	Accepted	8ms	356 KiB
			77	Accepted	9ms	396 KiB
			78	Accepted	8ms	228 KiB
			79	Accepted	9ms	396 KiB
			80	Accepted	8ms	300 KiB
			81	Accepted	9ms	256 KiB
			82	Accepted	10ms	300 KiB
			83	Accepted	12ms	360 KiB
			84	Accepted	12ms	384 KiB
			85	Accepted	12ms	360 KiB
			86	Accepted	9ms	512 KiB
			87	Accepted	8ms	256 KiB
			88	Accepted	10ms	416 KiB
			89	Accepted	43ms	316 KiB
			90	Accepted	32ms	492 KiB
			91	Accepted	43ms	420 KiB
			92	Accepted	37ms	420 KiB
			93	Accepted	50ms	536 KiB
			94	Accepted	41ms	424 KiB
			95	Accepted	41ms	384 KiB
			96	Accepted	45ms	528 KiB
			97	Accepted	45ms	356 KiB
			98	Accepted	54ms	420 KiB
			99	Accepted	57ms	360 KiB
			100	Accepted	46ms	532 KiB
			101	Accepted	46ms	492 KiB
			102	Accepted	46ms	384 KiB
			103	Accepted	50ms	384 KiB
			104	Accepted	981ms	432 KiB
			105	Accepted	986ms	484 KiB
			106	Accepted	984ms	544 KiB
			107	Accepted	976ms	440 KiB
			108	Accepted	981ms	428 KiB
			109	Accepted	1.013s	540 KiB
			110	Accepted	1.016s	424 KiB
			111	Accepted	995ms	428 KiB
			112	Accepted	972ms	432 KiB
			113	Accepted	991ms	496 KiB
			114	Accepted	986ms	488 KiB
			115	Accepted	977ms	484 KiB
			116	Accepted	1.023s	484 KiB
			117	Accepted	1.037s	424 KiB
			118	Accepted	1.039s	552 KiB
			119	Accepted	1.041s	432 KiB
			120	Accepted	1.031s	428 KiB
			121	Accepted	1.004s	428 KiB
			122	Accepted	999ms	372 KiB
123	Accepted		986ms	428 KiB
124	Accepted		995ms	444 KiB
125	Accepted		981ms	424 KiB
126	Accepted		1.031s	532 KiB
127	Accepted		1.049s	548 KiB
128	Accepted		1.05s	500 KiB
129	Accepted		1.039s	436 KiB
130	Accepted		1.026s	420 KiB
131	Accepted		967ms	428 KiB
132	Accepted		958ms	484 KiB