QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#765493 | #8267. Staring Contest | _8_8_# | 0 | 3ms | 12776kb | C++20 | 4.1kb | 2024-11-20 14:26:27 | 2024-11-20 14:26:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int)1500 + 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 mem[N][N];
int get(int i, int j) {
if(mem[i][j] != -1) return mem[i][j];
c++;
if(loc) return min(a[i], a[j]);
cout << "? " << i << ' ' << j << endl;
int x;
cin >> x;
return mem[i][j] = mem[j][i] = 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;
}
vector<array<int, 3>> f;
vector<int> y;
vector<int> vis(n + 1, 0);
while(!x.empty()) {
int j = x.back();
x.pop_back();
if(vis[j]) continue;
bool ok = 0;
for(int r = 0; r < (int)x.size() - 1; r++) {
if(mem[x[r]][j] != -1) {
f.push_back({get(x[r], j), x[r], j});
vis[x[r]] = 1;
ok = 1;
break;
}
}
if(!ok) {
y.push_back(j);
}
}
x = y;
int m = (int)x.size();
vector<int> nx;
if(m & 1) {
x.pop_back();
}
m--;
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 {
if(nv[0] < bf[0]) res[nv[2]] = nv[0];
else{
res[bf[2]] = bf[0];
bf = nv;
}
}
}
for(int i = 1; i <= n; i++) {
if(!res[i]) {
nx.push_back(i);
}
}
assert((int)nx.size() <= (int)x.size() / 2 + 2);
solve(nx);
}
bool check() {
int c = 0;
for(int i = 1; i <= n; i++) {
if(res[i] > a[i]) return false;
if(res[i] < a[i]) c++;
}
return (c <= 1);
}
bool str = 0;
void test() {
memset(mem, -1, sizeof(mem));
for(int i = 1; i <= n; i++) {
res[i] = 0;
}
if(!str) {
cin >> n;
if(loc) {
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
}
}
vector<int> f(n);
iota(f.begin(), f.end(), 1);
shuffle(f.begin(), f.end(), rng);
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;
}
if(!str) {
cout << "! ";
for(int i = 1; i <= n; i++) {
cout << res[i] << ' ';
}
}
}
void stress() {
loc = str = 1;
for(int i = 1; i <= 100; i++) {
n = 1500;
for(int j = 1; j <= n; j++) {
a[j] = j;
}
shuffle(a + 1, a + n + 1, rng);
c = 0;
test();
cout << c << '\n';
if(!check()) {
for(int j = 1; j <= n; j++) {
cout << a[j] << ' ';
}
cout << '\n';
for(int j = 1; j <= n; j++) {
cout << res[j] << ' ';
}
cout << '\n';
exit(0);
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// stress();
// return 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
Runtime Error
Test #1:
score: 9
Accepted
time: 3ms
memory: 12776kb
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: 3ms
memory: 12528kb
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: 0ms
memory: 12556kb
input:
2 1
output:
? 2 1 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #4:
score: 0
Runtime Error
input:
50 4 1 30 3 20 27 9 12 31 23 22 17 8 13 47 21 28 11 10 26 2 6 5 15 38 19 5 16 2 26 10 42 42 21 42 41 18 40 22 33 32 14 35 39 20 7 30 47 4 49 43 40 37 35 33 29 24 18 14 16 19 25 32 34 36 39 41 44 42 1
output:
? 4 44 ? 48 1 ? 30 36 ? 7 3 ? 20 29 ? 39 27 ? 35 9 ? 14 12 ? 32 31 ? 33 23 ? 22 24 ? 40 17 ? 18 8 ? 41 13 ? 47 50 ? 21 43 ? 45 28 ? 46 11 ? 10 25 ? 26 49 ? 2 34 ? 16 6 ? 5 37 ? 19 15 ? 42 38 ? 19 42 ? 5 42 ? 16 42 ? 2 42 ? 26 42 ? 10 42 ? 46 42 ? 45 42 ? 21 42 ? 47 42 ? 41 47 ? 18 47 ? 40 47 ? 22 47...
result:
Subtask #2:
score: 0
Runtime Error
Test #58:
score: 0
Runtime Error
input:
1000 274 73 331 419 124 391 92 8 759 176 687 347 104 119 123 295 584 86 502 405 700 213 384 250 29 933 139 767 19 444 513 671 282 230 363 196 219 820 459 627 383 330 202 431 120 107 189 111 456 623 650 39 234 300 14 106 553 74 606 496 536 1 77 469 400 927 2 897 3 351 516 173 241 277 576 180 198 957 ...
output:
? 995 274 ? 315 73 ? 482 331 ? 419 550 ? 124 369 ? 979 391 ? 92 914 ? 438 8 ? 759 803 ? 757 176 ? 687 898 ? 971 347 ? 104 186 ? 555 119 ? 123 338 ? 295 596 ? 816 584 ? 86 158 ? 502 714 ? 863 405 ? 700 751 ? 213 561 ? 890 384 ? 903 250 ? 97 29 ? 956 933 ? 212 139 ? 767 860 ? 604 19 ? 965 444 ? 513 77...
result:
Subtask #3:
score: 0
Runtime Error
Test #88:
score: 0
Runtime Error
input:
1500 120 452 1359 633 490 534 194 596 450 709 663 104 715 503 80 545 299 550 184 711 45 76 381 1224 264 478 509 531 618 175 753 664 26 268 786 823 479 144 394 339 386 987 226 842 1089 197 861 400 285 981 1017 372 169 309 291 695 641 441 256 1039 293 319 951 397 1055 759 220 72 246 434 162 156 267 56...
output:
? 120 313 ? 517 452 ? 1386 1359 ? 633 1167 ? 490 500 ? 877 534 ? 194 661 ? 673 596 ? 450 1106 ? 1175 709 ? 663 1214 ? 104 123 ? 1475 715 ? 503 1259 ? 80 236 ? 836 545 ? 299 890 ? 550 794 ? 184 1369 ? 1052 711 ? 45 1293 ? 1290 76 ? 381 1097 ? 1439 1224 ? 756 264 ? 662 478 ? 509 852 ? 531 1105 ? 1257 ...