164652025-05-02 10:36:53szilKutyák és macskákcpp17Részben helyes 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva804ms1692 KiB
subtask26/6
3Elfogadva745ms1596 KiB
4Elfogadva760ms1784 KiB
5Elfogadva737ms1596 KiB
6Elfogadva778ms1600 KiB
7Elfogadva769ms1588 KiB
subtask37/7
8Elfogadva2ms564 KiB
9Elfogadva2ms508 KiB
10Elfogadva2ms316 KiB
11Elfogadva2ms316 KiB
12Elfogadva2ms316 KiB
13Elfogadva27ms684 KiB
14Elfogadva35ms720 KiB
subtask410/10
15Elfogadva8ms316 KiB
16Elfogadva8ms408 KiB
17Elfogadva8ms316 KiB
18Elfogadva8ms564 KiB
19Elfogadva8ms512 KiB
20Elfogadva7ms316 KiB
21Elfogadva8ms564 KiB
22Elfogadva8ms508 KiB
23Elfogadva8ms316 KiB
24Elfogadva8ms316 KiB
25Elfogadva8ms316 KiB
26Elfogadva8ms316 KiB
27Elfogadva8ms316 KiB
28Elfogadva8ms316 KiB
29Elfogadva8ms564 KiB
subtask512/12
30Elfogadva8ms316 KiB
31Elfogadva8ms408 KiB
32Elfogadva8ms316 KiB
33Elfogadva8ms564 KiB
34Elfogadva8ms512 KiB
35Elfogadva7ms316 KiB
36Elfogadva8ms564 KiB
37Elfogadva8ms508 KiB
38Elfogadva8ms316 KiB
39Elfogadva8ms316 KiB
40Elfogadva8ms316 KiB
41Elfogadva8ms316 KiB
42Elfogadva8ms316 KiB
43Elfogadva8ms316 KiB
44Elfogadva8ms564 KiB
45Elfogadva39ms412 KiB
46Elfogadva39ms508 KiB
47Elfogadva39ms564 KiB
48Elfogadva39ms456 KiB
49Elfogadva45ms568 KiB
50Elfogadva39ms688 KiB
51Elfogadva39ms668 KiB
52Elfogadva39ms592 KiB
53Elfogadva43ms928 KiB
54Elfogadva41ms564 KiB
55Elfogadva46ms668 KiB
56Elfogadva43ms468 KiB
57Elfogadva43ms508 KiB
58Elfogadva41ms828 KiB
59Elfogadva46ms564 KiB
subtask656.43/65
60Elfogadva1ms320 KiB
61Elfogadva787ms1788 KiB
62Elfogadva745ms1596 KiB
63Elfogadva760ms1784 KiB
64Elfogadva737ms1596 KiB
65Elfogadva778ms1600 KiB
66Elfogadva769ms1588 KiB
67Elfogadva2ms564 KiB
68Elfogadva2ms508 KiB
69Elfogadva2ms316 KiB
70Elfogadva2ms316 KiB
71Elfogadva2ms316 KiB
72Elfogadva27ms684 KiB
73Elfogadva35ms720 KiB
74Elfogadva8ms316 KiB
75Elfogadva8ms408 KiB
76Elfogadva8ms316 KiB
77Elfogadva8ms564 KiB
78Elfogadva8ms512 KiB
79Elfogadva7ms316 KiB
80Elfogadva8ms564 KiB
81Elfogadva8ms508 KiB
82Elfogadva8ms316 KiB
83Elfogadva8ms316 KiB
84Elfogadva8ms316 KiB
85Elfogadva8ms316 KiB
86Elfogadva8ms316 KiB
87Elfogadva8ms316 KiB
88Elfogadva8ms564 KiB
89Elfogadva39ms412 KiB
90Elfogadva39ms508 KiB
91Elfogadva39ms564 KiB
92Elfogadva39ms456 KiB
93Elfogadva45ms568 KiB
94Elfogadva39ms688 KiB
95Elfogadva39ms668 KiB
96Elfogadva39ms592 KiB
97Elfogadva43ms928 KiB
98Elfogadva41ms564 KiB
99Elfogadva46ms668 KiB
100Elfogadva43ms468 KiB
101Elfogadva43ms508 KiB
102Elfogadva41ms828 KiB
103Elfogadva46ms564 KiB
104Részben helyes785ms1684 KiB
105Részben helyes800ms1696 KiB
106Részben helyes792ms1636 KiB
107Részben helyes783ms1976 KiB
108Részben helyes773ms1652 KiB
109Részben helyes768ms1608 KiB
110Részben helyes763ms1652 KiB
111Elfogadva740ms1688 KiB
112Elfogadva836ms2000 KiB
113Elfogadva814ms1816 KiB
114Részben helyes805ms1816 KiB
115Részben helyes750ms1696 KiB
116Részben helyes830ms1692 KiB
117Részben helyes860ms1884 KiB
118Részben helyes788ms2168 KiB
119Részben helyes768ms1688 KiB
120Részben helyes857ms1664 KiB
121Részben helyes824ms1820 KiB
122Részben helyes757ms1668 KiB
123Részben helyes787ms1708 KiB
124Részben helyes790ms1896 KiB
125Részben helyes763ms1900 KiB
126Részben helyes769ms1588 KiB
127Részben helyes808ms1660 KiB
128Részben helyes806ms1876 KiB
129Részben helyes768ms1488 KiB
130Részben helyes773ms1668 KiB
131Részben helyes787ms1704 KiB
132Részben helyes777ms1844 KiB