110222024-06-13 06:57:00hogyKutyák és macskákcpp17Elfogadva 100/1001.05s612 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());
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms356 KiB
2Elfogadva908ms612 KiB
subtask26/6
3Elfogadva984ms424 KiB
4Elfogadva985ms504 KiB
5Elfogadva1.001s360 KiB
6Elfogadva972ms508 KiB
7Elfogadva961ms484 KiB
subtask37/7
8Elfogadva4ms436 KiB
9Elfogadva4ms548 KiB
10Elfogadva3ms408 KiB
11Elfogadva4ms504 KiB
12Elfogadva4ms396 KiB
13Elfogadva28ms384 KiB
14Elfogadva35ms384 KiB
subtask410/10
15Elfogadva8ms356 KiB
16Elfogadva8ms384 KiB
17Elfogadva8ms356 KiB
18Elfogadva9ms396 KiB
19Elfogadva8ms228 KiB
20Elfogadva9ms396 KiB
21Elfogadva8ms300 KiB
22Elfogadva9ms256 KiB
23Elfogadva10ms300 KiB
24Elfogadva12ms360 KiB
25Elfogadva12ms384 KiB
26Elfogadva12ms360 KiB
27Elfogadva9ms512 KiB
28Elfogadva8ms256 KiB
29Elfogadva10ms416 KiB
subtask512/12
30Elfogadva8ms356 KiB
31Elfogadva8ms384 KiB
32Elfogadva8ms356 KiB
33Elfogadva9ms396 KiB
34Elfogadva8ms228 KiB
35Elfogadva9ms396 KiB
36Elfogadva8ms300 KiB
37Elfogadva9ms256 KiB
38Elfogadva10ms300 KiB
39Elfogadva12ms360 KiB
40Elfogadva12ms384 KiB
41Elfogadva12ms360 KiB
42Elfogadva9ms512 KiB
43Elfogadva8ms256 KiB
44Elfogadva10ms416 KiB
45Elfogadva43ms316 KiB
46Elfogadva32ms492 KiB
47Elfogadva43ms420 KiB
48Elfogadva37ms420 KiB
49Elfogadva50ms536 KiB
50Elfogadva41ms424 KiB
51Elfogadva41ms384 KiB
52Elfogadva45ms528 KiB
53Elfogadva45ms356 KiB
54Elfogadva54ms420 KiB
55Elfogadva57ms360 KiB
56Elfogadva46ms532 KiB
57Elfogadva46ms492 KiB
58Elfogadva46ms384 KiB
59Elfogadva50ms384 KiB
subtask665/65
60Elfogadva3ms376 KiB
61Elfogadva977ms428 KiB
62Elfogadva984ms424 KiB
63Elfogadva985ms504 KiB
64Elfogadva1.001s360 KiB
65Elfogadva972ms508 KiB
66Elfogadva961ms484 KiB
67Elfogadva4ms436 KiB
68Elfogadva4ms548 KiB
69Elfogadva3ms408 KiB
70Elfogadva4ms504 KiB
71Elfogadva4ms396 KiB
72Elfogadva28ms384 KiB
73Elfogadva35ms384 KiB
74Elfogadva8ms356 KiB
75Elfogadva8ms384 KiB
76Elfogadva8ms356 KiB
77Elfogadva9ms396 KiB
78Elfogadva8ms228 KiB
79Elfogadva9ms396 KiB
80Elfogadva8ms300 KiB
81Elfogadva9ms256 KiB
82Elfogadva10ms300 KiB
83Elfogadva12ms360 KiB
84Elfogadva12ms384 KiB
85Elfogadva12ms360 KiB
86Elfogadva9ms512 KiB
87Elfogadva8ms256 KiB
88Elfogadva10ms416 KiB
89Elfogadva43ms316 KiB
90Elfogadva32ms492 KiB
91Elfogadva43ms420 KiB
92Elfogadva37ms420 KiB
93Elfogadva50ms536 KiB
94Elfogadva41ms424 KiB
95Elfogadva41ms384 KiB
96Elfogadva45ms528 KiB
97Elfogadva45ms356 KiB
98Elfogadva54ms420 KiB
99Elfogadva57ms360 KiB
100Elfogadva46ms532 KiB
101Elfogadva46ms492 KiB
102Elfogadva46ms384 KiB
103Elfogadva50ms384 KiB
104Elfogadva981ms432 KiB
105Elfogadva986ms484 KiB
106Elfogadva984ms544 KiB
107Elfogadva976ms440 KiB
108Elfogadva981ms428 KiB
109Elfogadva1.013s540 KiB
110Elfogadva1.016s424 KiB
111Elfogadva995ms428 KiB
112Elfogadva972ms432 KiB
113Elfogadva991ms496 KiB
114Elfogadva986ms488 KiB
115Elfogadva977ms484 KiB
116Elfogadva1.023s484 KiB
117Elfogadva1.037s424 KiB
118Elfogadva1.039s552 KiB
119Elfogadva1.041s432 KiB
120Elfogadva1.031s428 KiB
121Elfogadva1.004s428 KiB
122Elfogadva999ms372 KiB
123Elfogadva986ms428 KiB
124Elfogadva995ms444 KiB
125Elfogadva981ms424 KiB
126Elfogadva1.031s532 KiB
127Elfogadva1.049s548 KiB
128Elfogadva1.05s500 KiB
129Elfogadva1.039s436 KiB
130Elfogadva1.026s420 KiB
131Elfogadva967ms428 KiB
132Elfogadva958ms484 KiB