164652025-05-02 10:36:53szilKutyák és macskákcpp17Partially correct 91.43/100860ms2168 KiB
#include "KutyakMacskak.h"
#include <bits/stdc++.h>

using namespace std;

map<vector<int>, int> cache;

int ask2(int a, int b, int c) {
    if (b > c) swap(b, c);
    if (!cache.count({a, b, c})) cache[{a, b, c}] = ask(a, b, c);
    
    return cache[{a, b, c}];
}

void merge_sort(vector<int> &arr, const function<bool(int,int)> &func) {
    if (arr.size() > 1) {
        vector<int> arr1(arr.begin(), arr.begin()+arr.size()/2);
        vector<int> arr2(arr.begin()+arr.size()/2, arr.end());
        merge_sort(arr1, func);
        merge_sort(arr2, func);

        vector<int> res;
        merge(arr1.begin(), arr1.end(), arr2.begin(), arr2.end(), back_inserter(res), func);
        arr = res;
    }
}

std::vector<int> find_order(int N, int M) {
    cache.clear();
    swap(N, M);
    int best = 1;
    for (int i = 2; i <= N; i++) {
        if (ask2(1, best, i) == best) best = i;
    }
    int ptr = 1, kutya = -1;
    for (int i = 1; i <= M; i++) {
        for (; ptr <= N; ptr++) {
            if (ptr == best) continue;
            if (ask2(i, ptr, best) == ptr) {
                break;
            }
        }
        if (ptr > N) {
            kutya = i;
            break;
        }
    }
    vector<int> ord(N);
    iota(ord.begin(), ord.end(), 1);

    merge_sort(ord, [&](int a, int b){
        return ask2(kutya, a, b) == a;
    });

    return ord;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted804ms1692 KiB
subtask26/6
3Accepted745ms1596 KiB
4Accepted760ms1784 KiB
5Accepted737ms1596 KiB
6Accepted778ms1600 KiB
7Accepted769ms1588 KiB
subtask37/7
8Accepted2ms564 KiB
9Accepted2ms508 KiB
10Accepted2ms316 KiB
11Accepted2ms316 KiB
12Accepted2ms316 KiB
13Accepted27ms684 KiB
14Accepted35ms720 KiB
subtask410/10
15Accepted8ms316 KiB
16Accepted8ms408 KiB
17Accepted8ms316 KiB
18Accepted8ms564 KiB
19Accepted8ms512 KiB
20Accepted7ms316 KiB
21Accepted8ms564 KiB
22Accepted8ms508 KiB
23Accepted8ms316 KiB
24Accepted8ms316 KiB
25Accepted8ms316 KiB
26Accepted8ms316 KiB
27Accepted8ms316 KiB
28Accepted8ms316 KiB
29Accepted8ms564 KiB
subtask512/12
30Accepted8ms316 KiB
31Accepted8ms408 KiB
32Accepted8ms316 KiB
33Accepted8ms564 KiB
34Accepted8ms512 KiB
35Accepted7ms316 KiB
36Accepted8ms564 KiB
37Accepted8ms508 KiB
38Accepted8ms316 KiB
39Accepted8ms316 KiB
40Accepted8ms316 KiB
41Accepted8ms316 KiB
42Accepted8ms316 KiB
43Accepted8ms316 KiB
44Accepted8ms564 KiB
45Accepted39ms412 KiB
46Accepted39ms508 KiB
47Accepted39ms564 KiB
48Accepted39ms456 KiB
49Accepted45ms568 KiB
50Accepted39ms688 KiB
51Accepted39ms668 KiB
52Accepted39ms592 KiB
53Accepted43ms928 KiB
54Accepted41ms564 KiB
55Accepted46ms668 KiB
56Accepted43ms468 KiB
57Accepted43ms508 KiB
58Accepted41ms828 KiB
59Accepted46ms564 KiB
subtask656.43/65
60Accepted1ms320 KiB
61Accepted787ms1788 KiB
62Accepted745ms1596 KiB
63Accepted760ms1784 KiB
64Accepted737ms1596 KiB
65Accepted778ms1600 KiB
66Accepted769ms1588 KiB
67Accepted2ms564 KiB
68Accepted2ms508 KiB
69Accepted2ms316 KiB
70Accepted2ms316 KiB
71Accepted2ms316 KiB
72Accepted27ms684 KiB
73Accepted35ms720 KiB
74Accepted8ms316 KiB
75Accepted8ms408 KiB
76Accepted8ms316 KiB
77Accepted8ms564 KiB
78Accepted8ms512 KiB
79Accepted7ms316 KiB
80Accepted8ms564 KiB
81Accepted8ms508 KiB
82Accepted8ms316 KiB
83Accepted8ms316 KiB
84Accepted8ms316 KiB
85Accepted8ms316 KiB
86Accepted8ms316 KiB
87Accepted8ms316 KiB
88Accepted8ms564 KiB
89Accepted39ms412 KiB
90Accepted39ms508 KiB
91Accepted39ms564 KiB
92Accepted39ms456 KiB
93Accepted45ms568 KiB
94Accepted39ms688 KiB
95Accepted39ms668 KiB
96Accepted39ms592 KiB
97Accepted43ms928 KiB
98Accepted41ms564 KiB
99Accepted46ms668 KiB
100Accepted43ms468 KiB
101Accepted43ms508 KiB
102Accepted41ms828 KiB
103Accepted46ms564 KiB
104Partially correct785ms1684 KiB
105Partially correct800ms1696 KiB
106Partially correct792ms1636 KiB
107Partially correct783ms1976 KiB
108Partially correct773ms1652 KiB
109Partially correct768ms1608 KiB
110Partially correct763ms1652 KiB
111Accepted740ms1688 KiB
112Accepted836ms2000 KiB
113Accepted814ms1816 KiB
114Partially correct805ms1816 KiB
115Partially correct750ms1696 KiB
116Partially correct830ms1692 KiB
117Partially correct860ms1884 KiB
118Partially correct788ms2168 KiB
119Partially correct768ms1688 KiB
120Partially correct857ms1664 KiB
121Partially correct824ms1820 KiB
122Partially correct757ms1668 KiB
123Partially correct787ms1708 KiB
124Partially correct790ms1896 KiB
125Partially correct763ms1900 KiB
126Partially correct769ms1588 KiB
127Partially correct808ms1660 KiB
128Partially correct806ms1876 KiB
129Partially correct768ms1488 KiB
130Partially correct773ms1668 KiB
131Partially correct787ms1704 KiB
132Partially correct777ms1844 KiB