QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#765329 | #8267. Staring Contest | _8_8_# | 0 | 4ms | 5924kb | C++20 | 2.4kb | 2024-11-20 13:54:21 | 2024-11-20 13:54:21 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1e6 + 12;
const ll inf = (ll)1e18;
int c = 0;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(123121);
int n, p, res[N], a[N];
bool loc = 0;
int get(int i, int j) {
c++;
assert(c <= 3000);
cout << "? " << i << ' ' << j << endl;
if(loc) return min(a[i], a[j]);
int x;
cin >> x;
return x;
}
void solve(vector<int> x) {
if((int)x.size() <= 1) return;
if((int)x.size() == 2) {
int val = get(x[0], x[1]);
res[x[0]] = res[x[1]] = val;
return;
}
if((int)x.size() == 3) {
int val = get(x[0], x[1]);
int val1 = get(x[1], x[2]);
if(val == val1) {
res[x[1]] = val;
solve({x[0], x[2]});
return;
} else {
res[x[0]] = val;
res[x[1]] = max(val, val1);
res[x[2]] = val1;
}
return;
}
int m = (int)x.size();
vector<int> nx;
if(m & 1) {
x.pop_back();
}
m--;
vector<array<int, 3>> f;
for(int i = 0; i < m; i += 2) {
f.push_back({get(x[i], x[i + 1]), x[i], x[i + 1]});
}
array<int, 3> bf = f.back();
f.pop_back();
while(!f.empty()) {
array<int, 3> nv = f.back();
f.pop_back();
int val = get(nv[1], bf[1]);
if(val == nv[0]) {
res[nv[1]] = val;
} else if(val == bf[0]) {
res[bf[1]] = val;
bf = nv;
} else {
res[nv[2]] = nv[0];
res[bf[2]] = bf[0];
}
}
for(int i = 1; i <= n; i++) {
if(!res[i]) {
nx.push_back(i);
}
}
solve(nx);
}
void test() {
cin >> n;
if(loc) {
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
}
vector<int> f(n);
iota(f.begin(), f.end(), 1);
solve(f);
int mx = 0;
for(int i = 1; i <= n; i++) {
mx = max(mx ,res[i]);
}
for(int i =1; i <= n; i++) {
if(!res[i]) res[i] = mx;
}
cout << "! ";
for(int i = 1; i <= n; i++) {
cout << res[i] << ' ';
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 9
Accepted
time: 1ms
memory: 5924kb
input:
2 1
output:
? 1 2 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #2:
score: 9
Accepted
time: 1ms
memory: 5684kb
input:
2 1
output:
? 1 2 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #3:
score: 9
Accepted
time: 1ms
memory: 5644kb
input:
2 1
output:
? 1 2 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #4:
score: 9
Accepted
time: 2ms
memory: 5700kb
input:
50 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 47 45 43 41 39 37 35 33 31 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1 2 6 10 14 18 22 26 30 34 38 42 46 49 46 42 38 34 30 26 22 18 14 10 6 2 4 12 20 28 36 44 49 44 36 28 20 12 4 8 24 40 49 40 24 8 16 48 16 32 49 32 48 49
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 47 49 ? 45 49 ? 43 49 ? 41 49 ? 39 49 ? 37 49 ? 35 49 ? 33 49 ? 31 49 ? 29 49 ? 27 49 ? 25 49 ? 23 49 ? 21 ...
result:
points 1.0 points 1.0 n = 50, you used 102 queries
Test #5:
score: 9
Accepted
time: 0ms
memory: 5760kb
input:
50 49 47 45 43 41 39 37 35 33 31 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 48 44 40 36 32 28 24 20 16 12 8 4 6 6 6 6 6 6 6 6 6 6 6 46 38 30 22 14 6 10 10 10 10 10 42 26 10 18 18 34 2 18 18
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 47 49 ? 45 49 ? 43 49 ? 41 49 ? 39 49 ? 37 49 ? 35 49 ? 33 49 ? 31 49 ? 29 49 ? 27 49 ? 25 49 ? 23 49 ? 21 ...
result:
points 1.0 points 1.0 n = 50, you used 92 queries
Test #6:
score: 0
Wrong Answer
time: 1ms
memory: 5888kb
input:
50 1 5 9 13 17 21 25 29 33 37 41 45 49 46 42 38 34 30 26 22 18 14 10 6 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 1 3 9 17 25 33 41 48 40 32 24 16 8 12 12 12 12 12 12 12 12 12 9 3 5 17 33 44 28 12 20 20 20 17 5 13 33 20 33 13 25 20 25 36 4 20 20
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 47 49 ? 45 49 ? 43 49 ? 41 49 ? 39 49 ? 37 49 ? 35 49 ? 33 49 ? 31 49 ? 29 49 ? 27 49 ? 25 49 ? 23 49 ? 21 ...
result:
wrong answer mismatched on more than one position
Subtask #2:
score: 0
Wrong Answer
Test #58:
score: 11
Accepted
time: 0ms
memory: 5776kb
input:
1000 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 17...
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 51 52 ? 53 54 ? 55 56 ? 57 58 ? 59 60 ? 61 62 ? 63 64 ? 65 66 ? 67 68 ? 69 70 ? 71 72 ? 73 74 ? 75 76 ? 77 ...
result:
points 1.0 points 1.0 n = 1000, you used 2006 queries
Test #59:
score: 11
Accepted
time: 0ms
memory: 5652kb
input:
1000 999 997 995 993 991 989 987 985 983 981 979 977 975 973 971 969 967 965 963 961 959 957 955 953 951 949 947 945 943 941 939 937 935 933 931 929 927 925 923 921 919 917 915 913 911 909 907 905 903 901 899 897 895 893 891 889 887 885 883 881 879 877 875 873 871 869 867 865 863 861 859 857 855 853...
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 51 52 ? 53 54 ? 55 56 ? 57 58 ? 59 60 ? 61 62 ? 63 64 ? 65 66 ? 67 68 ? 69 70 ? 71 72 ? 73 74 ? 75 76 ? 77 ...
result:
points 1.0 points 1.0 n = 1000, you used 1988 queries
Test #60:
score: 0
Wrong Answer
time: 4ms
memory: 5720kb
input:
1000 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 97 101 105 109 113 117 121 125 129 133 137 141 145 149 153 157 161 165 169 173 177 181 185 189 193 197 201 205 209 213 217 221 225 229 233 237 241 245 249 253 257 261 265 269 273 277 281 285 289 293 297 301 305 309 313 317 321...
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 51 52 ? 53 54 ? 55 56 ? 57 58 ? 59 60 ? 61 62 ? 63 64 ? 65 66 ? 67 68 ? 69 70 ? 71 72 ? 73 74 ? 75 76 ? 77 ...
result:
wrong answer mismatched on more than one position
Subtask #3:
score: 0
Runtime Error
Test #88:
score: 0
Runtime Error
input:
1500 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 17...
output:
? 1 2 ? 3 4 ? 5 6 ? 7 8 ? 9 10 ? 11 12 ? 13 14 ? 15 16 ? 17 18 ? 19 20 ? 21 22 ? 23 24 ? 25 26 ? 27 28 ? 29 30 ? 31 32 ? 33 34 ? 35 36 ? 37 38 ? 39 40 ? 41 42 ? 43 44 ? 45 46 ? 47 48 ? 49 50 ? 51 52 ? 53 54 ? 55 56 ? 57 58 ? 59 60 ? 61 62 ? 63 64 ? 65 66 ? 67 68 ? 69 70 ? 71 72 ? 73 74 ? 75 76 ? 77 ...