QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #749921 | #8363. interactive | xcc_szy0905 | 10 | 9ms | 4284kb | C++14 | 930b | 2024-11-15 11:25:01 | 2024-11-15 11:25:02 |
Judging History
answer
#include<bits/stdc++.h>
#include "interactive.h"
using namespace std;
const int kmaxn=505;
vector<int>an;
int dm[kmaxn][kmaxn];
int n;
void dfs(int x,int f){
an.push_back(x);
for(int i=1;i<=n;i++){
if(dm[x][i]&&i!=f&&i!=x){
dfs(i,x);
}
}
}
std::vector<int> solve(int N){
n=N;
srand(time(0));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dm[i][j]=100;
}
}
vector<int>pr;
for(int i=1;i<=n;i++){
pr.push_back(i);
}
for(int I=1;I<=25000;I++){
random_shuffle(pr.begin(),pr.end());
int op=query(pr);
if(n==3){
if(op==2){
return pr;
}
}
for(int i=0;i<n-1;i++){
int u=pr[i],v=pr[i+1];
dm[u][v]=min(dm[u][v],op);
dm[v][u]=min(dm[v][u],op);
}
}
for(int i=1;i<=n;i++){
int sz=0;
for(int j=1;j<=n;j++){
// cout<<i<<" "<<j<<" "<<dm[i][j]<<"\n";
if(i!=j&&dm[i][j])sz++;
}
if(sz==1){dfs(i,0);return an;}
}
return an;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3872kb
input:
1 3 3 1 2
output:
1 26286 7113
result:
points 1.0
Test #2:
score: 10
Accepted
time: 6ms
memory: 4016kb
input:
1 30 6 28 10 9 13 4 7 1 21 15 20 27 19 5 17 2 22 12 29 23 14 30 18 3 11 24 26 16 8 25
output:
25000 554394559 537621159
result:
points 1.0
Test #3:
score: 10
Accepted
time: 9ms
memory: 3984kb
input:
1 27 24 17 15 3 13 9 6 16 14 22 7 19 25 12 1 26 23 27 10 21 8 5 18 11 20 4 2
output:
25000 554394559 966160455
result:
points 1.0
Test #4:
score: 10
Accepted
time: 6ms
memory: 4284kb
input:
1 29 24 8 7 14 19 20 4 6 1 12 18 2 10 3 23 13 26 11 22 27 9 17 16 5 21 29 25 15 28
output:
25000 554394559 646167394
result:
points 1.0
Test #5:
score: 10
Accepted
time: 9ms
memory: 3984kb
input:
1 30 9 22 10 27 8 5 23 21 2 25 6 13 30 19 17 20 4 14 29 28 24 15 11 7 12 18 26 16 3 1
output:
25000 554394559 904341262
result:
points 1.0
Test #6:
score: 10
Accepted
time: 8ms
memory: 3972kb
input:
1 27 8 6 11 20 24 7 9 25 13 19 2 3 23 15 16 4 22 21 10 18 12 27 14 5 1 17 26
output:
25000 554394559 173992498
result:
points 1.0
Test #7:
score: 10
Accepted
time: 5ms
memory: 3984kb
input:
1 27 2 5 25 13 11 12 23 24 6 18 19 21 15 17 7 10 16 20 22 27 3 4 8 14 26 1 9
output:
25000 554394559 772894146
result:
points 1.0
Test #8:
score: 10
Accepted
time: 9ms
memory: 3948kb
input:
1 27 13 11 10 27 20 23 3 25 12 24 6 2 19 9 7 17 1 5 8 26 14 16 21 15 22 4 18
output:
25000 554394559 181323461
result:
points 1.0
Test #9:
score: 10
Accepted
time: 9ms
memory: 3988kb
input:
1 27 3 15 12 14 18 27 23 6 20 26 21 5 13 19 10 9 11 17 16 4 25 7 24 2 22 1 8
output:
25000 554394559 480249695
result:
points 1.0
Test #10:
score: 10
Accepted
time: 9ms
memory: 4272kb
input:
1 29 23 7 4 10 9 16 1 14 3 17 13 19 15 8 5 22 24 29 11 12 18 25 21 2 28 26 27 20 6
output:
25000 554394559 31142540
result:
points 1.0
Subtask #2:
score: 0
Memory Limit Exceeded
Test #11:
score: 90
Accepted
time: 9ms
memory: 3988kb
input:
1 27 17 16 3 20 27 5 2 13 24 21 25 23 19 9 7 4 22 12 26 15 14 11 1 18 6 10 8
output:
25000 554394559 558749364
result:
points 1.0
Test #12:
score: 90
Accepted
time: 9ms
memory: 3952kb
input:
1 29 19 13 20 22 26 1 23 24 3 14 8 25 29 17 10 9 15 11 18 4 2 28 21 7 6 12 16 27 5
output:
25000 554394559 145445666
result:
points 1.0
Test #13:
score: 90
Accepted
time: 9ms
memory: 3984kb
input:
1 28 16 7 19 9 23 12 20 26 4 10 15 8 21 5 1 22 27 2 18 24 28 6 3 14 13 17 25 11
output:
25000 554394559 877668399
result:
points 1.0
Test #14:
score: 90
Accepted
time: 9ms
memory: 4280kb
input:
1 30 13 4 29 25 16 14 6 15 19 28 7 20 3 23 12 17 8 22 1 24 9 30 21 18 2 26 27 10 11 5
output:
25000 554394559 737974315
result:
points 1.0
Test #15:
score: 90
Accepted
time: 9ms
memory: 3920kb
input:
1 27 18 25 15 20 23 14 4 16 27 6 2 12 21 19 17 26 9 8 10 11 3 7 13 22 24 5 1
output:
25000 554394559 590934171
result:
points 1.0
Test #16:
score: 0
Memory Limit Exceeded
input:
2 494 364 164 445 359 288 412 15 377 91 481 14 3 357 358 269 136 336 106 392 200 50 388 33 338 114 11 266 186 170 239 494 196 395 68 36 423 378 218 342 275 67 240 120 86 134 356 190 323 123 339 187 30 270 430 292 121 372 404 94 143 454 309 461 344 141 480 474 248 199 42 150 260 369 483 493 124 396 4...
output:
Unauthorized output