| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 260370 |
2020-08-10T07:27:57 Z |
임성재(#5050) |
Library (JOI18_library) |
C++17 |
|
370 ms |
764 KB |
#include "library.h"
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mp make_pair
static int p[1010];
static vector<int> M;
static vector<int> v[1010];
int n;
static void cl() {
for(int i=0; i<n; i++) M[i] = 0;
}
static int Find(int a) {
return p[a] = p[a] == a ? a : Find(p[a]);
}
static void Union(int a, int b) {
a = Find(a);
b = Find(b);
p[b] = a;
cl();
M[v[a].back() - 1] = M[v[b].front() - 1] = 1;
if(Query(M) == 1) {
for(auto i : v[b]) {
v[a].eb(i);
}
v[b].clear();
return;
}
reverse(all(v[b]));
cl();
M[v[a].back() - 1] = M[v[b].front() - 1] = 1;
if(Query(M) == 1) {
for(auto i : v[b]) {
v[a].eb(i);
}
v[b].clear();
return;
}
reverse(all(v[a]));
cl();
M[v[a].back() - 1] = M[v[b].front() - 1] = 1;
if(Query(M) == 1) {
for(auto i : v[b]) {
v[a].eb(i);
}
v[b].clear();
return;
}
reverse(all(v[b]));
cl();
M[v[a].back() - 1] = M[v[b].front() - 1] = 1;
if(Query(M) == 1) {
for(auto i : v[b]) {
v[a].eb(i);
}
v[b].clear();
return;
}
}
void f(int s, int e, int x, int k) {
if(s == e) {
Union(s, x);
return;
}
int m = (s + e) / 2;
cl();
M[x-1] = 1;
int t = 1;
for(int i=s; i<=m; i++) {
if(Find(i) != i) continue;
t++;
for(auto j : v[i]) {
M[j-1] = 1;
}
}
t -= Query(M);
if(t) f(s, m, x, t);
if(k - t) f(m+1, e, x, k-t);
}
void Solve(int N)
{
n = N;
for(int i=1; i<=N; i++)
p[i] = i, v[i].eb(i);
M.resize(N, 0);
int sz = 0;
for(int i=1; i<=N; i++) {
cl();
for(int j=1; j<=i; j++) M[j-1] = 1;
int k = Query(M);
if(k < sz + 1) f(1, i-1, i, sz + 1 - k);
sz = k;
}
for(int i=1; i<=N; i++) {
if(Find(i) == i) {
Answer(v[i]);
return;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
384 KB |
# of queries: 1747 |
| 2 |
Correct |
37 ms |
384 KB |
# of queries: 1762 |
| 3 |
Correct |
30 ms |
384 KB |
# of queries: 1809 |
| 4 |
Correct |
35 ms |
512 KB |
# of queries: 1793 |
| 5 |
Correct |
26 ms |
436 KB |
# of queries: 1827 |
| 6 |
Correct |
34 ms |
504 KB |
# of queries: 1842 |
| 7 |
Correct |
38 ms |
384 KB |
# of queries: 1816 |
| 8 |
Correct |
28 ms |
384 KB |
# of queries: 1739 |
| 9 |
Correct |
30 ms |
384 KB |
# of queries: 1847 |
| 10 |
Correct |
17 ms |
400 KB |
# of queries: 1073 |
| 11 |
Correct |
0 ms |
384 KB |
# of queries: 1 |
| 12 |
Correct |
1 ms |
384 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
384 KB |
# of queries: 8 |
| 14 |
Correct |
1 ms |
384 KB |
# of queries: 13 |
| 15 |
Correct |
1 ms |
384 KB |
# of queries: 78 |
| 16 |
Correct |
3 ms |
384 KB |
# of queries: 160 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
384 KB |
# of queries: 1747 |
| 2 |
Correct |
37 ms |
384 KB |
# of queries: 1762 |
| 3 |
Correct |
30 ms |
384 KB |
# of queries: 1809 |
| 4 |
Correct |
35 ms |
512 KB |
# of queries: 1793 |
| 5 |
Correct |
26 ms |
436 KB |
# of queries: 1827 |
| 6 |
Correct |
34 ms |
504 KB |
# of queries: 1842 |
| 7 |
Correct |
38 ms |
384 KB |
# of queries: 1816 |
| 8 |
Correct |
28 ms |
384 KB |
# of queries: 1739 |
| 9 |
Correct |
30 ms |
384 KB |
# of queries: 1847 |
| 10 |
Correct |
17 ms |
400 KB |
# of queries: 1073 |
| 11 |
Correct |
0 ms |
384 KB |
# of queries: 1 |
| 12 |
Correct |
1 ms |
384 KB |
# of queries: 3 |
| 13 |
Correct |
1 ms |
384 KB |
# of queries: 8 |
| 14 |
Correct |
1 ms |
384 KB |
# of queries: 13 |
| 15 |
Correct |
1 ms |
384 KB |
# of queries: 78 |
| 16 |
Correct |
3 ms |
384 KB |
# of queries: 160 |
| 17 |
Correct |
329 ms |
564 KB |
# of queries: 11487 |
| 18 |
Correct |
370 ms |
504 KB |
# of queries: 11396 |
| 19 |
Correct |
363 ms |
760 KB |
# of queries: 11440 |
| 20 |
Correct |
340 ms |
764 KB |
# of queries: 10733 |
| 21 |
Correct |
327 ms |
384 KB |
# of queries: 10140 |
| 22 |
Correct |
306 ms |
508 KB |
# of queries: 11473 |
| 23 |
Correct |
320 ms |
568 KB |
# of queries: 11455 |
| 24 |
Correct |
102 ms |
508 KB |
# of queries: 5336 |
| 25 |
Correct |
297 ms |
384 KB |
# of queries: 11233 |
| 26 |
Correct |
277 ms |
632 KB |
# of queries: 10519 |
| 27 |
Correct |
107 ms |
424 KB |
# of queries: 5338 |
| 28 |
Correct |
311 ms |
508 KB |
# of queries: 10966 |
| 29 |
Correct |
319 ms |
384 KB |
# of queries: 10954 |
| 30 |
Correct |
306 ms |
432 KB |
# of queries: 10966 |
