QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#765713 | #8267. Staring Contest | _8_8_# | 0 | 0ms | 12812kb | C++20 | 4.2kb | 2024-11-20 15:04:22 | 2024-11-20 15:04:22 |
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(val > max(nv[0], bf[0])) {
res[nv[2]] = nv[0];
res[bf[2]] = bf[0];
}
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;
}
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 9
Accepted
time: 0ms
memory: 12608kb
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: 0ms
memory: 12772kb
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: 12812kb
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 28 6 1 27 11 3 4 9 20 2 19 32 39 23 31 16 30 8 46 26 14 10 18 5 33 5 33 12 17 26 49 25 30 22 48 23 39 32 34 2 20 47 43 37 11 27 1 6 40 47 44 42 40 37 35 29 24 17 13 15 21 25 34 36 38 41 43 45 12 22
output:
? 40 28 ? 6 21 ? 1 15 ? 27 36 ? 11 13 ? 37 3 ? 43 4 ? 47 9 ? 20 45 ? 2 24 ? 34 19 ? 32 35 ? 39 42 ? 23 38 ? 48 31 ? 22 16 ? 30 44 ? 25 8 ? 50 46 ? 26 29 ? 17 14 ? 12 10 ? 49 18 ? 5 7 ? 33 41 ? 5 33 ? 49 33 ? 12 49 ? 17 49 ? 26 49 ? 50 49 ? 25 50 ? 30 50 ? 22 50 ? 48 50 ? 23 50 ? 39 50 ? 32 50 ? 34 5...
result:
Subtask #2:
score: 0
Runtime Error
Test #58:
score: 0
Runtime Error
input:
1000 547 132 589 197 579 54 236 70 843 249 328 642 206 586 233 671 179 284 194 410 283 52 50 214 419 681 784 593 432 113 212 434 685 544 312 144 3 89 226 295 569 215 453 555 437 740 146 11 319 115 38 375 392 692 898 619 710 102 348 80 210 114 620 174 293 739 156 417 618 93 152 573 452 464 648 818 55...
output:
? 939 547 ? 943 132 ? 858 589 ? 197 601 ? 579 647 ? 856 54 ? 637 236 ? 147 70 ? 848 843 ? 918 249 ? 613 328 ? 659 642 ? 206 986 ? 586 980 ? 822 233 ? 838 671 ? 179 330 ? 805 284 ? 337 194 ? 919 410 ? 283 857 ? 182 52 ? 924 50 ? 916 214 ? 419 694 ? 681 753 ? 825 784 ? 593 967 ? 720 432 ? 660 113 ? 23...
result:
Subtask #3:
score: 0
Runtime Error
Test #88:
score: 0
Runtime Error
input:
1500 83 575 457 489 248 581 46 683 637 1027 705 1234 616 439 937 171 477 441 163 630 1117 58 770 304 700 124 1031 834 587 838 622 505 95 815 75 409 401 546 882 299 287 98 311 866 610 56 177 282 1411 25 267 643 273 343 645 52 486 162 176 398 123 251 1038 547 675 1037 592 553 319 718 217 93 663 232 20...
output:
? 1094 83 ? 932 575 ? 1120 457 ? 934 489 ? 755 248 ? 1309 581 ? 46 558 ? 841 683 ? 637 1113 ? 1346 1027 ? 705 1380 ? 1234 1316 ? 616 1258 ? 548 439 ? 937 1281 ? 871 171 ? 477 650 ? 498 441 ? 1095 163 ? 630 1454 ? 1117 1485 ? 646 58 ? 1330 770 ? 900 304 ? 700 793 ? 1373 124 ? 1031 1197 ? 834 1194 ? 5...