QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #464828 | #4205. Art Collections | Dan4Life | 0 | 1286ms | 66360kb | C++23 | 1.3kb | 2024-07-06 15:17:03 | 2024-07-06 15:17:03 |
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)*.3+.5; 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
Memory Limit Exceeded
Test #1:
score: 0
Memory Limit Exceeded
input:
6 7 6 7 12 9 8 3 3 5 3 2 3 1 1
output:
942318468 6 4 3 2 6 1 5 942318468 6 2 6 4 5 1 3 942318468 6 3 2 6 4 5 1 942318468 6 1 3 2 6 4 5 942318468 6 5 1 3 2 6 4 942318468 6 4 5 1 3 2 6 942318468 6 6 4 5 1 3 2 942318468 6 6 4 5 2 1 3 942318468 6 4 5 6 2 1 3 942318468 6 5 6 4 2 1 3 942318468 6 6 5 4 2 1 3 942318468 6 6 5 4 1 2 3 942318468 6 ...
result:
Subtask #2:
score: 0
Memory Limit Exceeded
Test #8:
score: 0
Memory Limit Exceeded
input:
40 468 356 375 378 365 358 387 424 437 432 433 416 443 450 423 422 437 476 451 430 435 404 435 398 363 374 351 318 351 322 345 354 339 360 341 366 357 374 409 406 367 184 165 177 177 165 155 161 171 175 177 185 183 177 169 148 150 146 144 144 143 145 145 144
output:
942318468 40 38 25 2 36 35 5 12 4 10 29 19 32 39 18 27 20 40 6 17 9 16 23 28 13 26 30 33 31 7 3 14 34 15 8 1 11 21 37 24 22 942318468 40 21 39 14 25 12 3 28 10 18 9 6 40 24 2 37 35 31 5 16 17 8 27 23 34 15 29 32 13 36 30 33 26 22 4 20 38 19 1 11 7 942318468 40 7 21 39 14 25 12 3 28 10 18 9 6 40 24 2...
result:
Subtask #3:
score: 0
Runtime Error
Test #14:
score: 0
Runtime Error
input:
250 15249 14303 14418 14565 14638 14693 14474 14517 14722 14857 14750 14707 14956 15017 15042 14991 15170 15361 15502 15407 15550 15641 15708 15745 15740 15693 15762 15825 15676 15913 16062 16207 16172 16127 16038 16175 16006 16199 16014 16071 16070 15909 15688 15605 15758 15987 16106 16119 16020 16...
output:
942318468 250 95 106 23 19 55 123 109 57 105 176 222 169 239 179 215 114 89 63 173 2 201 33 98 17 66 155 227 29 142 158 148 207 200 140 238 12 103 18 221 62 159 228 97 110 163 146 115 127 125 145 147 76 248 225 220 49 249 9 245 226 219 56 34 21 53 138 43 46 180 47 224 204 93 70 108 231 137 94 190 26...
result:
Subtask #4:
score: 0
Memory Limit Exceeded
Test #20:
score: 0
Memory Limit Exceeded
input:
444 45771 51755 51752 51417 51730 51763 51880 51793 51726 51351 51786 52107 51742 52111 52166 51853 51552 51887 52244 51987 51954 52235 52394 52005 52236 52425 52166 52393 52662 52569 52436 52863 52688 52383 52772 53145 53522 53359 53236 53459 53414 53199 53536 53221 53636 53199 53350 53399 53250 53...
output:
942318468 444 95 270 338 19 336 123 109 253 354 274 222 169 239 374 215 412 89 63 173 317 201 257 301 410 66 353 227 365 328 158 148 207 342 140 238 334 444 18 296 62 159 287 97 346 355 146 115 127 125 145 147 76 292 225 220 49 249 429 245 298 219 321 423 310 425 303 364 46 180 47 413 399 422 358 30...
result:
Subtask #5:
score: 0
Memory Limit Exceeded
Test #26:
score: 0
Memory Limit Exceeded
input:
2000 977877 971560 971153 972852 973959 973000 972395 972526 972699 972146 972641 972990 971403 972030 973775 973282 974985 974356 973807 973644 973023 973298 974101 972700 974083 974318 974075 972914 972869 973266 974787 974794 973411 974708 974007 974744 973571 971640 972083 974062 973017 974346 9...
output:
942318468 2000 1416 1690 1838 269 1947 1989 1524 6 1174 189 1285 97 585 157 1069 167 1835 1969 1189 834 410 293 653 188 408 987 99 687 1432 1935 1652 935 288 327 268 1337 790 766 298 1724 254 48 874 478 741 1431 535 595 1698 1779 4 967 1641 1602 1546 1982 222 300 263 905 1864 174 1463 1246 808 1118 ...
result:
Subtask #6:
score: 0
Wrong Answer
Test #32:
score: 0
Wrong Answer
time: 1286ms
memory: 66360kb
input:
4000 3950327 4027013 4027632 4025143 4021822 4017961 4015926 4017347 4015802 4013819 4016776 4013715 4011730 4014309 4015804 4013265 4015830 4018659 4016638 4020027 4023812 4019869 4019454 4019809 4020776 4019737 4022672 4022955 4022702 4025543 4023994 4021647 4018606 4016387 4020252 4021615 4022920...
output:
942318468 4000 3193 836 2257 3782 1498 1579 1069 3907 3426 3551 1553 1446 2140 3702 2383 3074 28 3869 90 1065 2958 3763 298 169 3639 1994 162 830 379 2302 2839 3829 2392 943 1808 979 1767 1482 2259 2457 2104 3428 3553 1624 181 124 3164 2653 2602 1527 48 384 776 2955 787 413 706 3331 2563 108 2018 59...
result:
wrong answer Too many queries