| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 823878 |
2023-08-13T09:23:57 Z |
Kahou |
Library (JOI18_library) |
C++14 |
|
210 ms |
1076 KB |
#include<bits/stdc++.h>
#include"library.h"
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1050;
int n;
deque<int> dq[MAXN];
vector<int> get(int k) {
vector<int> out(n);
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (dq[i].empty()) continue;
cnt++;
if (cnt > k) break;
for (int x:dq[i]) {
out[x-1] = 1;
}
}
return out;
}
int getid(int x) {
for (int i = 1; i <= n; i++) {
if (dq[i].empty()) continue;
x--;
if (!x) return i;
}
return 0;
}
void Solve(int N) {
n = N;
int t = 1;
dq[1].push_back(1);
vector<int> vc(n);
for (int i = 2; i <= n; i++) {
vc = get(t);
vc[i-1] = 1;
int nt = Query(vc);
if (nt > t) {
dq[i].push_back(i);
t++;
}
else if (nt == t) {
int dw = 0, up = t;
while (up-dw > 1) {
int md = (up+dw)>>1;
vc = get(md);
vc[i-1] = 1;
if (Query(vc) > md) dw = md;
else up = md;
}
int id = getid(up);
bool flg = 0;
if (dq[id].size() > 1) {
fill(vc.begin(), vc.end(), 0);
for (int x:dq[id]) vc[x-1] = 1;
vc[i-1] = 1;
vc[dq[id].back()-1] = 0;
flg = (Query(vc) > 1);
}
if (flg) dq[id].push_back(i);
else dq[id].push_front(i);
}
else if (nt < t) {
int dw = 0, up = t;
while (up-dw > 1) {
int md = (up+dw)>>1;
vc = get(md);
vc[i-1] = 1;
if (Query(vc) > md) dw = md;
else up = md;
}
int A = getid(up);
dw = 0, up = t;
while (up-dw > 1) {
int md = (up+dw)>>1;
vc = get(md);
vc[i-1] = 1;
if (Query(vc) >= md) dw = md;
else up = md;
}
int B = getid(up);
bool flgA = 0, flgB = 0;
if (dq[A].size() > 1) {
fill(vc.begin(), vc.end(), 0);
for (int x : dq[A]) vc[x-1] = 1;
vc[i-1] = 1;
vc[dq[A].back()-1] = 0;
flgA = (Query(vc) > 1);
}
if (dq[B].size() > 1) {
fill(vc.begin(), vc.end(), 0);
for (int x : dq[B]) vc[x-1] = 1;
vc[i-1] = 1;
vc[dq[B].back()-1] = 0;
flgB = (Query(vc) > 1);
}
if (flgA) dq[A].push_back(i);
else dq[A].push_front(i);
if (flgB) reverse(dq[B].begin(), dq[B].end());
for (int x:dq[B]) {
if (flgA) dq[A].push_back(x);
else dq[A].push_front(x);
}
dq[B].clear();
t--;
}
}
vector<int> out;
for (int x:dq[1]) {
out.push_back(x);
}
Answer(out);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
976 KB |
# of queries: 1253 |
| 2 |
Correct |
13 ms |
1008 KB |
# of queries: 1259 |
| 3 |
Correct |
10 ms |
976 KB |
# of queries: 1309 |
| 4 |
Correct |
15 ms |
1008 KB |
# of queries: 1315 |
| 5 |
Correct |
17 ms |
976 KB |
# of queries: 1320 |
| 6 |
Correct |
13 ms |
976 KB |
# of queries: 1303 |
| 7 |
Correct |
17 ms |
1028 KB |
# of queries: 1316 |
| 8 |
Correct |
19 ms |
976 KB |
# of queries: 1246 |
| 9 |
Correct |
18 ms |
976 KB |
# of queries: 1309 |
| 10 |
Correct |
10 ms |
1016 KB |
# of queries: 765 |
| 11 |
Correct |
1 ms |
976 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
976 KB |
# of queries: 1 |
| 13 |
Correct |
1 ms |
976 KB |
# of queries: 3 |
| 14 |
Correct |
1 ms |
976 KB |
# of queries: 6 |
| 15 |
Correct |
1 ms |
976 KB |
# of queries: 48 |
| 16 |
Correct |
2 ms |
1012 KB |
# of queries: 108 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
976 KB |
# of queries: 1253 |
| 2 |
Correct |
13 ms |
1008 KB |
# of queries: 1259 |
| 3 |
Correct |
10 ms |
976 KB |
# of queries: 1309 |
| 4 |
Correct |
15 ms |
1008 KB |
# of queries: 1315 |
| 5 |
Correct |
17 ms |
976 KB |
# of queries: 1320 |
| 6 |
Correct |
13 ms |
976 KB |
# of queries: 1303 |
| 7 |
Correct |
17 ms |
1028 KB |
# of queries: 1316 |
| 8 |
Correct |
19 ms |
976 KB |
# of queries: 1246 |
| 9 |
Correct |
18 ms |
976 KB |
# of queries: 1309 |
| 10 |
Correct |
10 ms |
1016 KB |
# of queries: 765 |
| 11 |
Correct |
1 ms |
976 KB |
# of queries: 0 |
| 12 |
Correct |
1 ms |
976 KB |
# of queries: 1 |
| 13 |
Correct |
1 ms |
976 KB |
# of queries: 3 |
| 14 |
Correct |
1 ms |
976 KB |
# of queries: 6 |
| 15 |
Correct |
1 ms |
976 KB |
# of queries: 48 |
| 16 |
Correct |
2 ms |
1012 KB |
# of queries: 108 |
| 17 |
Correct |
210 ms |
1068 KB |
# of queries: 8817 |
| 18 |
Correct |
174 ms |
1072 KB |
# of queries: 8709 |
| 19 |
Correct |
172 ms |
1068 KB |
# of queries: 8767 |
| 20 |
Correct |
148 ms |
1040 KB |
# of queries: 8243 |
| 21 |
Correct |
153 ms |
1072 KB |
# of queries: 7729 |
| 22 |
Correct |
192 ms |
1036 KB |
# of queries: 8825 |
| 23 |
Correct |
184 ms |
1072 KB |
# of queries: 8805 |
| 24 |
Correct |
53 ms |
1036 KB |
# of queries: 4050 |
| 25 |
Correct |
188 ms |
1076 KB |
# of queries: 8624 |
| 26 |
Correct |
197 ms |
1028 KB |
# of queries: 8069 |
| 27 |
Correct |
68 ms |
1028 KB |
# of queries: 4018 |
| 28 |
Correct |
58 ms |
1016 KB |
# of queries: 1997 |
| 29 |
Correct |
63 ms |
1004 KB |
# of queries: 1995 |
| 30 |
Correct |
45 ms |
1004 KB |
# of queries: 1997 |
