QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#765473 | #8267. Staring Contest | _8_8_# | 0 | 3ms | 12740kb | C++20 | 4.1kb | 2024-11-20 14:23:52 | 2024-11-20 14:23:52 |
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--;
// shuffle(x.begin(), x.end(), rng);
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: 12516kb
input:
2 1
output:
? 2 1 ! 1 1
result:
points 1.0 points 1.0 n = 2, you used 1 queries
Test #2:
score: 9
Accepted
time: 3ms
memory: 12740kb
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: 12576kb
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 12 38 4 2 13 21 3 8 32 6 7 35 20 5 30 14 11 25 9 16 18 45 28 1 19 19 28 40 37 22 39 36 11 14 30 5 26 35 31 6 33 43 23 34 13 41 4 38 29 48 46 44 42 40 37 34 31 27 24 17 10 15 23 26 29 33 36 39 41 43 45 47 22 45 15 26 33 39 43 47 23
output:
? 29 12 ? 38 42 ? 4 15 ? 41 2 ? 13 17 ? 34 21 ? 23 3 ? 43 8 ? 33 32 ? 6 10 ? 31 7 ? 35 48 ? 26 20 ? 5 24 ? 30 44 ? 14 27 ? 11 46 ? 36 25 ? 39 9 ? 22 16 ? 37 18 ? 50 45 ? 28 47 ? 40 1 ? 19 49 ? 40 19 ? 28 40 ? 50 40 ? 37 50 ? 22 50 ? 39 50 ? 36 50 ? 11 50 ? 14 50 ? 30 50 ? 5 50 ? 26 50 ? 35 50 ? 31 5...
result:
Subtask #2:
score: 0
Runtime Error
Test #58:
score: 0
Runtime Error
input:
1000 500 232 123 67 227 340 97 226 376 567 740 579 690 390 255 260 194 248 98 99 22 525 88 471 584 208 279 298 475 657 625 497 568 676 239 29 600 50 768 190 246 109 8 304 154 148 158 391 271 837 629 611 293 69 74 578 122 168 534 301 521 531 217 224 408 724 244 320 542 132 425 49 451 36 403 198 786 2...
output:
? 500 664 ? 422 232 ? 779 123 ? 594 67 ? 544 227 ? 490 340 ? 956 97 ? 226 533 ? 516 376 ? 697 567 ? 852 740 ? 776 579 ? 941 690 ? 527 390 ? 709 255 ? 537 260 ? 194 372 ? 606 248 ? 98 447 ? 99 461 ? 889 22 ? 771 525 ? 88 552 ? 720 471 ? 746 584 ? 208 991 ? 811 279 ? 575 298 ? 475 945 ? 887 657 ? 965 ...
result:
Subtask #3:
score: 0
Runtime Error
Test #88:
score: 0
Runtime Error
input:
1500 1 535 706 154 837 293 304 231 402 383 637 233 222 1107 460 10 568 628 695 165 554 619 162 73 886 89 115 388 305 46 548 90 18 690 969 609 84 83 294 1344 478 28 465 623 666 272 1022 537 63 791 606 423 134 1227 494 1051 43 428 442 686 269 499 104 768 885 1302 1445 775 232 493 597 61 194 374 69 588...
output:
? 1070 1 ? 721 535 ? 706 1254 ? 1035 154 ? 837 1397 ? 293 1139 ? 576 304 ? 1058 231 ? 402 1471 ? 383 1363 ? 637 1231 ? 233 1458 ? 222 332 ? 1411 1107 ? 667 460 ? 10 1283 ? 1125 568 ? 801 628 ? 695 1389 ? 1387 165 ? 554 1358 ? 1406 619 ? 1401 162 ? 73 705 ? 1483 886 ? 1073 89 ? 115 716 ? 1034 388 ? 3...