QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#798027 | #8363. interactive | L_Wave | 10 | 93ms | 10116kb | C++20 | 4.0kb | 2024-12-03 23:21:37 | 2024-12-03 23:21:39 |
Judging History
answer
// Problem: #P13098. 交互题
// Author: XZC(L_Wave)
// Language: Cpp/G++20
// Contest: Hydro
// URL: http://www.nfls.com.cn:10611/p/5472
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// Create Time: not 2024-12-03 20:49:39, but 1926-08-17 11:45:14
//
// Powered by CP Editor (https://cpeditor.org)
#ifndef LOCAL
#include"interactive.h"
#else
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <numeric>
std::vector<int> solve(int n);
int query(std::vector<int> vec);
#define rep0(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
using namespace std;
namespace
{
const int MAXN = 500, MAXQ = 300000;
int n, ty, p[505], mat[505][505], cnt;
bool vis[505];
bool legal(const vector<int>& arr)
{
if((int)arr.size() != n) return false;
rep1(i, n) vis[i] = false;
rep0(i, arr.size()) {
if(arr[i] < 1 || arr[i] > n || vis[arr[i]]) return false;
vis[arr[i]] = true;
}
return true;
}
}
int query(vector<int> arr)
{
if(cnt == MAXQ || !legal(arr)) {
printf("WA: 0\n"); exit(0);
}
int ret = 0;
rep0(i, (int)arr.size() - 1) ret += mat[arr[i]][arr[i + 1]];
cnt ++;
return ret;
}
int main()
{
scanf("%d%d", &ty, &n);
iota(p+1,p+n+1,1);
if (ty==1)
rep1(i, n) scanf("%d", &p[i]);
rep1(i, n - 1) mat[p[i]][p[i + 1]] = mat[p[i + 1]][p[i]] = 1;
vector<int> ans = solve(n);
if(!legal(ans)) printf("WA: 1\n");
else {
int sum = 0;
rep0(i, n - 1) sum += mat[ans[i]][ans[i + 1]];
if(sum == n - 1) printf("AC: %d\n", cnt);
else printf("WA: 1\n");
}
exit(0);
}
#endif
#include <bits/stdc++.h>
#undef rep
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
namespace local{
vector<int>res;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int id[505][505],p[505],n;
long double w[505][505];
bool vis[505];
void dfs(int u){
// cout<<u<<'\n';
res.push_back(u);
vis[u]=1;
rep(v,1,n)if (!vis[id[u][v]]){
dfs(id[u][v]);
return ;
}
}
int ask(){
vector<int>Q;
rep(i,1,n)Q.push_back(p[i]);
return query(Q);
}
void adj(vector<pair<int,int>>V,long double val){
val/=V.size();
int t;
if (val>=0.8)t=5;
else t=10;
for (auto [x,y]:V)w[x][y]=w[y][x]=(w[x][y]*t+val)/(t+1);
}
std::vector<int> solve(int _n){
n=_n;
iota(p+1,p+n+1,1);
rep(i,1,n)rep(j,1,n){
if (i^j)w[i][j]=2.l/n;
else w[i][j]=-1e9;
}
rep(i,1,11500){
shuffle(p+1,p+n+1,rng);
int x=ask();
// cout<<"$$ "<<x<<'\n';
rep(t,1,n-1)if (w[p[t]][p[t+1]]>0.9999)--x;
if (!x){
rep(t,1,n-1)if (w[p[t]][p[t+1]]<=0.9999)w[p[t]][p[t+1]]=w[p[t+1]][p[t]]=-1e9;
// rep(i,1,n)rep(j,1,n)cout<<w[i][j]<<" \n"[j==n];
continue;
}
vector<pair<int,int>>V;
rep(t,1,n-1)if (w[p[t]][p[t+1]]>0&&w[p[t]][p[t+1]]<=0.9999)V.push_back({p[t],p[t+1]});
if (x==(int)V.size()){
for (auto [x,y]:V)w[x][y]=w[y][x]=1;
V.clear();
}
// if (V.size()==1)cout<<w[V[0].first][V[0].second]<<' '<<x<<'\n';
adj(V,x);
// if (V.size()==1)cout<<w[V[0].first][V[0].second]<<'\n';
// if (x==-1){
// rep(i,1,n)cout<<p[i]<<' ';
// cout<<'\n';
// rep(i,1,n-1)if (w[p[i]][p[i+1]]>0.9999)cout<<p[i]<<' '<<p[i+1]<<' '<<w[p[i]][p[i+1]]<<'\n';
// }
// rep(i,1,n)rep(j,1,n)cout<<w[i][j]<<" \n"[j==n];
}
int pos=0;
long double mx=0;
rep(i,1,n){
iota(id[i]+1,id[i]+n+1,1);
sort(id[i]+1,id[i]+n+1,[&](int x,int y){
return w[i][x]>w[i][y];
});
}
rep(i,1,n){
memset(vis,0,sizeof(vis));
res.clear();
dfs(i);
long double val=1;
rep(i,0,n-2)val=min(val,w[res[i]][res[i+1]]);
if (mx<val)mx=val,pos=i;
}
memset(vis,0,sizeof(vis));
res.clear();
dfs(pos);
return res;
}
}
std::vector<int> solve(int n){return local::solve(n);}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 2ms
memory: 6188kb
input:
1 3 3 1 2
output:
11500 829368322 7113
result:
points 1.0
Test #2:
score: 10
Accepted
time: 7ms
memory: 6084kb
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:
11500 829368322 537621159
result:
points 1.0
Test #3:
score: 10
Accepted
time: 3ms
memory: 6136kb
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:
11500 829368322 966160455
result:
points 1.0
Test #4:
score: 10
Accepted
time: 7ms
memory: 6124kb
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:
11500 829368322 646167394
result:
points 1.0
Test #5:
score: 10
Accepted
time: 3ms
memory: 7988kb
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:
11500 829368322 904341262
result:
points 1.0
Test #6:
score: 10
Accepted
time: 6ms
memory: 6012kb
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:
11500 829368322 173992498
result:
points 1.0
Test #7:
score: 10
Accepted
time: 6ms
memory: 6060kb
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:
11500 829368322 772894146
result:
points 1.0
Test #8:
score: 10
Accepted
time: 6ms
memory: 4052kb
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:
11500 829368322 181323461
result:
points 1.0
Test #9:
score: 10
Accepted
time: 6ms
memory: 4048kb
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:
11500 829368322 480249695
result:
points 1.0
Test #10:
score: 10
Accepted
time: 6ms
memory: 6068kb
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:
11500 829368322 31142540
result:
points 1.0
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 90
Accepted
time: 6ms
memory: 6132kb
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:
11500 829368322 558749364
result:
points 1.0
Test #12:
score: 90
Accepted
time: 6ms
memory: 6124kb
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:
11500 829368322 145445666
result:
points 1.0
Test #13:
score: 90
Accepted
time: 3ms
memory: 8120kb
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:
11500 829368322 877668399
result:
points 1.0
Test #14:
score: 90
Accepted
time: 6ms
memory: 4084kb
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:
11500 829368322 737974315
result:
points 1.0
Test #15:
score: 90
Accepted
time: 6ms
memory: 5984kb
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:
11500 829368322 590934171
result:
points 1.0
Test #16:
score: 79.5
Acceptable Answer
time: 91ms
memory: 10108kb
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:
11500 829368322 998930322
result:
points 0.88333333330
Test #17:
score: 79.5
Acceptable Answer
time: 91ms
memory: 9828kb
input:
2 500 468 70 339 65 443 143 75 123 220 163 390 484 489 139 392 147 183 132 202 14 19 380 310 259 179 482 85 36 232 419 285 378 137 274 376 23 321 263 217 485 387 466 94 104 164 57 185 359 42 211 40 206 418 184 458 173 441 291 11 366 428 384 223 190 374 34 275 210 171 226 408 168 88 494 204 66 481 10...
output:
11500 829368322 110390244
result:
points 0.88333333330
Test #18:
score: 79.5
Acceptable Answer
time: 88ms
memory: 9896kb
input:
2 500 217 120 312 323 22 113 331 295 315 66 434 181 381 421 154 253 226 100 152 490 389 261 244 249 165 500 4 426 23 487 356 466 364 436 2 374 486 494 420 14 344 34 26 475 279 96 457 493 185 147 227 41 180 61 472 102 76 131 141 164 324 204 403 298 283 284 19 132 258 355 499 183 108 483 348 172 134 2...
output:
11500 829368322 177306504
result:
points 0.88333333330
Test #19:
score: 79.5
Acceptable Answer
time: 90ms
memory: 9884kb
input:
2 496 483 115 328 488 147 188 287 16 251 1 30 170 224 187 15 156 61 366 232 472 474 92 10 457 228 28 109 261 229 480 7 84 180 65 313 239 380 359 464 339 471 484 356 485 435 352 220 454 430 113 39 494 311 149 396 81 346 226 145 345 354 402 298 433 99 208 289 424 79 97 300 93 186 425 470 383 183 165 2...
output:
11500 829368322 595257989
result:
points 0.88333333330
Test #20:
score: 79.5
Acceptable Answer
time: 81ms
memory: 10076kb
input:
2 498 275 455 229 213 132 452 185 346 279 90 113 30 162 148 69 1 154 11 310 66 435 153 86 52 467 477 201 12 121 238 84 67 5 436 401 496 340 6 463 411 343 360 88 473 57 396 14 106 144 22 98 472 422 149 25 168 59 363 165 323 112 317 127 383 46 68 212 138 389 330 4 361 200 203 492 50 263 355 242 33 267...
output:
11500 829368322 79267961
result:
points 0.88333333330
Test #21:
score: 79.5
Acceptable Answer
time: 92ms
memory: 9844kb
input:
2 499 218 441 27 245 323 157 414 380 126 423 444 273 440 438 226 292 418 115 81 420 412 342 263 446 219 114 108 38 253 146 54 496 150 450 103 147 44 19 353 80 310 70 384 91 13 413 386 161 396 61 349 409 221 367 96 322 227 433 201 231 175 64 290 402 495 373 233 211 94 162 31 95 176 330 289 295 52 102...
output:
11500 829368322 791732988
result:
points 0.88333333330
Test #22:
score: 79.5
Acceptable Answer
time: 86ms
memory: 9884kb
input:
2 494 154 75 65 20 92 153 39 236 177 41 482 47 298 426 124 228 494 381 473 364 128 109 340 57 432 480 144 43 184 392 286 359 291 423 469 260 468 355 146 231 28 235 62 188 134 138 305 87 175 362 95 58 116 250 464 297 254 407 212 32 160 316 453 396 18 243 338 272 252 454 199 422 249 418 450 185 356 39...
output:
11500 829368322 192551329
result:
points 0.88333333330
Test #23:
score: 79.5
Acceptable Answer
time: 92ms
memory: 9892kb
input:
2 493 118 473 190 268 244 72 211 196 153 261 12 76 245 365 371 162 302 352 112 272 273 425 340 354 234 220 45 65 231 321 290 285 383 389 83 133 248 260 376 326 214 33 478 323 3 373 334 437 212 457 337 47 81 113 339 379 173 421 223 253 48 314 312 55 408 363 258 42 160 289 82 239 472 359 415 465 80 35...
output:
11500 829368322 506886456
result:
points 0.88333333330
Test #24:
score: 79.5
Acceptable Answer
time: 91ms
memory: 9760kb
input:
2 493 491 357 122 219 398 79 375 33 186 118 298 2 206 132 140 99 465 251 350 120 474 35 218 131 355 173 158 478 388 349 100 418 149 156 124 482 437 221 200 29 31 61 489 208 414 188 479 358 72 134 52 416 263 88 187 115 392 104 214 233 48 74 411 146 341 332 71 144 351 32 477 265 421 461 238 352 222 20...
output:
11500 829368322 908595790
result:
points 0.88333333330
Test #25:
score: 79.5
Acceptable Answer
time: 91ms
memory: 9892kb
input:
2 494 456 311 174 150 206 61 33 444 53 256 331 131 148 105 1 370 133 269 406 407 310 29 293 153 232 469 122 480 334 300 195 94 422 59 36 308 217 288 193 197 476 392 239 417 204 222 50 488 491 432 181 77 137 145 23 64 276 90 250 106 270 76 179 173 279 164 34 12 124 388 182 4 273 474 154 235 87 291 21...
output:
11500 829368322 270167063
result:
points 0.88333333330
Test #26:
score: 79.5
Acceptable Answer
time: 87ms
memory: 9884kb
input:
2 500 454 477 317 465 497 59 428 162 66 19 144 293 396 332 404 381 184 330 469 476 187 96 92 114 296 119 152 20 218 110 417 61 10 173 56 385 350 470 389 192 165 429 243 25 325 359 94 401 288 340 183 190 137 366 194 89 500 252 103 392 356 8 175 88 6 220 221 322 108 46 15 134 98 121 5 199 277 105 453 ...
output:
11500 829368322 721976537
result:
points 0.88333333330
Test #27:
score: 79.5
Acceptable Answer
time: 92ms
memory: 9844kb
input:
2 499 106 154 51 308 314 251 211 424 476 279 11 33 441 226 132 233 388 55 153 430 322 466 232 30 71 218 48 67 285 317 345 219 220 473 378 293 56 422 142 451 239 241 456 2 370 409 117 309 152 341 377 471 198 7 134 170 301 62 302 438 349 222 131 12 41 284 497 209 176 121 3 420 163 407 468 18 141 405 3...
output:
11500 829368322 377700749
result:
points 0.88333333330
Test #28:
score: 79.5
Acceptable Answer
time: 91ms
memory: 10116kb
input:
2 495 423 23 335 113 489 190 353 192 20 420 126 200 428 288 329 247 457 487 94 58 439 331 25 289 401 97 95 80 488 389 171 176 79 153 410 185 444 223 193 84 201 93 89 239 441 469 285 385 112 54 486 375 120 82 330 21 350 491 316 429 136 433 104 337 49 460 338 109 290 319 14 286 314 406 356 218 449 61 ...
output:
11500 829368322 897331140
result:
points 0.88333333330
Test #29:
score: 79.5
Acceptable Answer
time: 92ms
memory: 9812kb
input:
2 499 457 89 410 105 251 213 370 21 400 343 112 363 127 246 67 295 46 450 401 181 204 280 197 362 499 385 178 75 36 24 226 34 313 155 309 38 383 311 284 236 8 217 461 4 406 39 434 238 119 439 224 374 129 87 120 43 244 388 276 165 272 211 292 492 498 287 28 467 124 209 445 344 184 33 416 373 130 351 ...
output:
11500 829368322 133945382
result:
points 0.88333333330
Test #30:
score: 79.5
Acceptable Answer
time: 91ms
memory: 9808kb
input:
2 495 156 72 312 345 94 199 108 380 440 453 459 444 200 362 363 82 433 223 90 153 313 323 219 202 162 487 339 109 116 129 256 135 394 232 340 43 403 95 79 277 77 483 247 303 477 264 158 8 482 410 282 184 209 488 149 48 452 6 229 242 274 371 419 144 217 93 117 243 69 292 408 5 390 15 305 160 450 173 ...
output:
11500 829368322 849918778
result:
points 0.88333333330
Test #31:
score: 79.5
Acceptable Answer
time: 93ms
memory: 9876kb
input:
2 500 67 132 292 289 258 397 128 475 102 395 428 215 379 346 36 158 270 264 63 205 321 470 274 331 243 330 12 232 389 286 39 310 498 336 266 247 212 374 3 392 91 423 66 345 437 47 375 438 487 354 364 210 410 472 37 171 33 340 111 355 217 229 167 439 248 141 284 317 154 489 53 136 112 79 461 348 325 ...
output:
11500 829368322 388419518
result:
points 0.88333333330
Test #32:
score: 79.5
Acceptable Answer
time: 87ms
memory: 9820kb
input:
2 499 51 157 140 16 135 464 326 332 373 489 265 48 191 145 224 488 10 351 232 214 178 216 200 427 290 487 160 444 79 177 52 275 65 425 130 60 363 327 114 496 31 29 380 466 57 286 113 207 453 12 348 448 74 92 163 370 316 294 246 369 272 474 213 235 317 159 438 172 260 197 381 4 146 473 439 103 269 41...
output:
11500 829368322 749259185
result:
points 0.88333333330
Test #33:
score: 0
Wrong Answer
time: 87ms
memory: 9816kb
input:
2 496 470 370 310 293 349 442 311 185 218 418 168 113 338 262 64 40 431 296 434 405 109 361 197 420 475 381 492 366 427 14 358 194 136 384 5 407 251 414 417 353 22 97 156 76 316 400 449 303 451 107 65 37 129 357 282 179 463 334 126 123 367 196 464 268 456 453 468 269 45 9 82 237 272 423 100 166 308 ...
output:
0 0 0
result:
FAIL WA