QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #464833 | #4205. Art Collections | Dan4Life | 0 | 1310ms | 66352kb | C++23 | 1.3kb | 2024-07-06 15:18:42 | 2024-07-06 15:18:43 |
Judging History
answer
#include "art.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ar2 = array<int,2>;
using ar3 = array<int,3>;
using ll = long long;
const int mxN = 4010;
int n;
vector<int> v;
bool better[mxN];
map<vector<int>,int> M;
int myPublish(vector<int> V){
if(M.count(V)) return M[V];
return M[V] = publish(V);
}
void recur(int l, int r){
if(l==r) return;
int xd = (r-l+1);
for(int i = l; i <= r; i++)
better[v[i]]=0;
int st = myPublish(v);
if(st==0) return;
random_shuffle(begin(v)+l,begin(v)+r+1);
int cnt = 0;
while(xd-- and cnt<=(r-l+1)/2){
int b = v[r];
v.erase(begin(v)+r);
v.insert(begin(v)+l,b);
int now = myPublish(v);
if(now <= st) better[b]=1,cnt++;
st = now;
}
vector<int> nw; nw.clear();
for(int i = 0; i < l; i++) nw.pb(v[i]);
for(int i = l; i <= r; i++) if(better[v[i]]) nw.pb(v[i]);
for(int i = l; i <= r; i++) if(!better[v[i]]) nw.pb(v[i]);
for(int i = r+1; i < n; i++) nw.pb(v[i]);
v.clear(); for(auto u : nw) v.pb(u);
int mid = (l+r)/2.1; recur(l,mid); recur(mid+1,r);
}
void solve(int N) {
n = N; srand(time(NULL));
v.resize(N,0);
iota(all(v),1);
random_shuffle(all(v));
recur(0,N-1); answer(v);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 1ms
memory: 3824kb
input:
6 7 7 8 7 10 5 10 4 5 3 5 1 0
output:
942318468 6 4 3 1 6 5 2 942318468 6 5 1 6 2 4 3 942318468 6 3 5 1 6 2 4 942318468 6 4 3 5 1 6 2 942318468 6 2 4 3 5 1 6 942318468 6 6 2 4 3 5 1 942318468 6 1 6 2 4 3 5 942318468 6 6 4 5 1 2 3 942318468 6 5 4 6 1 2 3 942318468 6 6 5 4 1 2 3 942318468 6 4 6 5 1 2 3 942318468 6 6 5 4 3 1 2 942318468 6 ...
result:
ok correct
Test #2:
score: -5
Wrong Answer
time: 0ms
memory: 3880kb
input:
6 5 11 8 3 4 7 12 6 9 7 7 8 5 4
output:
942318468 6 4 3 1 6 5 2 942318468 6 5 1 6 2 4 3 942318468 6 3 5 1 6 2 4 942318468 6 4 3 5 1 6 2 942318468 6 2 4 3 5 1 6 942318468 6 6 2 4 3 5 1 942318468 6 1 6 2 4 3 5 942318468 6 4 3 1 6 2 5 942318468 6 1 3 4 6 2 5 942318468 6 4 1 3 6 2 5 942318468 6 3 4 1 6 2 5 942318468 6 3 1 4 6 2 5 942318468 6 ...
result:
wrong answer Wrong Answer
Subtask #2:
score: 0
Memory Limit Exceeded
Test #8:
score: 0
Memory Limit Exceeded
input:
40 446 361 356 379 380 345 374 373 356 371 368 373 410 391 408 429 422 447 418 451 460 427 402 409 386 405 444 475 444 405 396 383 386 375 354 327 354 339 374 385 398 192 202 194 196 194 178 178 188 204 222 216 228 214 210 218 222 204 218 224 214 166 168 176 172 170 172 176 176 168 162 158 161 158 1...
output:
942318468 40 13 27 21 29 20 2 8 18 7 24 17 34 25 30 3 38 1 4 22 26 35 31 14 16 12 40 32 19 33 37 39 23 6 36 28 9 15 11 10 5 942318468 40 16 4 31 25 9 30 13 23 21 11 1 3 39 8 17 15 7 35 36 34 37 6 2 24 28 19 18 12 10 20 27 14 29 33 32 38 5 26 40 22 942318468 40 22 16 4 31 25 9 30 13 23 21 11 1 3 39 8...
result:
Subtask #3:
score: 0
Memory Limit Exceeded
Test #14:
score: 0
Memory Limit Exceeded
input:
250 16094 15061 15166 15281 15354 15523 15398 15483 15426 15297 15308 15541 15334 15159 14948 14711 14634 14741 14962 15083 15282 15319 15558 15389 15564 15639 15870 16083 15890 16029 15878 16001 15922 15881 16076 16159 16300 16103 16196 15987 15944 15853 16044 15925 15724 15739 15986 16175 16274 16...
output:
942318468 250 62 116 188 196 249 24 201 231 230 247 101 211 33 214 25 78 123 59 200 77 104 13 144 39 66 56 96 198 4 245 87 225 175 54 28 46 146 57 30 228 154 48 149 19 72 27 38 232 161 71 219 129 53 55 176 164 74 150 35 64 98 160 199 61 95 157 168 250 172 97 10 52 218 83 5 197 148 238 233 14 20 15 9...
result:
Subtask #4:
score: 0
Memory Limit Exceeded
Test #20:
score: 0
Memory Limit Exceeded
input:
444 51641 49988 49967 49912 49593 49430 49253 48878 48901 49072 49487 49382 48967 48984 49411 49136 49099 49174 49387 49356 49151 49514 49127 49064 49241 48836 48877 48724 48809 48946 49015 49188 48837 48756 48399 48130 47753 47638 47527 47694 48089 47786 47863 47850 48279 48552 48853 48850 48851 49...
output:
942318468 444 266 116 277 276 135 422 327 163 187 201 343 307 136 267 160 243 139 324 29 152 284 369 349 112 79 75 98 225 368 432 103 120 290 295 399 384 372 434 162 147 400 412 43 41 365 405 370 6 442 373 289 403 11 320 123 239 54 341 28 252 232 229 247 282 316 176 143 259 85 53 52 314 12 128 418 1...
result:
Subtask #5:
score: 0
Memory Limit Exceeded
Test #26:
score: 0
Memory Limit Exceeded
input:
2000 985088 1038935 1037486 1039025 1040070 1041065 1041316 1040089 1039918 1039101 1039006 1039407 1037408 1036167 1036382 1037497 1037268 1036759 1035694 1035333 1034912 1035563 1033742 1032337 1030872 1030997 1032522 1031989 1031242 1030109 1028234 1027817 1027550 1028055 1027034 1025671 1024204 ...
output:
942318468 2000 1675 1943 78 451 1461 1773 1676 1569 1006 836 877 361 393 84 980 71 428 1977 304 737 18 1211 1680 306 758 286 853 243 1118 857 1969 851 1988 1609 1460 201 1428 1209 1760 804 409 118 1631 3 1330 629 1660 1710 1253 638 1474 344 206 1639 285 1750 1201 1914 1919 1266 1303 1790 514 1771 67...
result:
Subtask #6:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 1310ms
memory: 66352kb
input:
4000 3927715 4028389 4025968 4027867 4029106 4030265 4028102 4031397 4031204 4027211 4024248 4020683 4020714 4017091 4016954 4019299 4023194 4021955 4019718 4021907 4022674 4025441 4028684 4029907 4031460 4035267 4037800 4036573 4032694 4032331 4033402 4031581 4027764 4025953 4024290 4022599 4022440...
output:
942318468 4000 1442 3764 1805 1712 478 3455 2724 1426 465 3437 1074 2539 795 105 2921 300 398 2536 182 3829 3085 2331 2217 1516 3063 1624 3679 1836 399 3185 2140 1937 3503 1059 3540 3487 269 918 2390 2492 3874 1862 3027 3314 1244 3722 1610 1050 1042 1757 330 3479 2988 1775 2192 2846 2972 3641 324 11...
result:
wrong answer Too many queries