#include <bits/stdc++.h>
#include <library.h>
using namespace std;
const int maxn = 1005;
int l[maxn], r[maxn];
int pai1[maxn], pai2[maxn];
vector<int> heads1, heads2;
int find1(int x){
return pai1[x] = pai1[x] == x ? x : find1(pai1[x]);
}
int find2(int x){
return pai2[x] = pai2[x] == x ? x : find2(pai2[x]);
}
int Q1(int tl, int tr, int i, int n){
if(tl == tr) return tl;
int mid = (tl+tr)>>1;
vector<int> q(n,0);
for(int j = tl; j <= mid; j++) q[find1(heads1[j])-1] = 1;
q[i-1] = 1;
int f = Query(q);
if(f == heads1.size()) return Q1(tl, mid, i, n);
return Q1(mid+1, tr, i, n);
}
int Q2(int tl, int tr, int i, int n){
if(tl == tr) return tl;
int mid = (tl+tr)>>1;
vector<int> q(n,0);
for(int j = tl; j <= mid; j++) q[find2(heads2[j])-1] = 1;
q[i-1] = 1;
int f = Query(q);
if(f == heads2.size()) return Q2(tl, mid, i, n);
return Q2(mid+1, tr, i, n);
}
void Solve(int n){
for(int i = 1; i <= n; i++) pai1[i] = pai2[i] = i;
memset(l, -1, sizeof(l)), memset(r, -1, sizeof(r));
for(int i = 1; i <= n; i++){
vector<int> q1(n,0);
for(auto j : heads1) q1[find2(j)-1] = 1;
q1[i-1] = 1;
int f = Query(q1);
if(f == heads1.size()+1){
heads1.push_back(i);
}
else{
int v = Q1(0, heads1.size(), i, n);
l[heads1[v]] = pai1[heads1[v]] = i;
heads1[v] = i;
}
// vector<int> q2(n,0);
// for(auto j : heads2) q2[find1(j)-1] = 1;
// q2[i-1] = 1;
// f = Query(q2);
// if(f == heads2.size()+1){
// heads2.push_back(i);
// }
// else{
// int v = Q1(0, heads1.size(), i, n);
// l[heads2[v]] = pai1[heads2[v]] = i;
// heads2[v] = i;
// }
}
int s;
for(int i = 1; i <= n; i++) if(l[i] == -1) s = i;
vector<int> ans(n);
ans[0] = s;
for(int i = 1; i < n; i++) ans[i] = l[ans[i-1]];
Answer(ans);
}
Compilation message
library.cpp: In function 'int Q1(int, int, int, int)':
library.cpp:25:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | if(f == heads1.size()) return Q1(tl, mid, i, n);
| ~~^~~~~~~~~~~~~~~~
library.cpp: In function 'int Q2(int, int, int, int)':
library.cpp:36:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | if(f == heads2.size()) return Q2(tl, mid, i, n);
| ~~^~~~~~~~~~~~~~~~
library.cpp: In function 'void Solve(int)':
library.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | if(f == heads1.size()+1){
| ~~^~~~~~~~~~~~~~~~~~
library.cpp:72:12: warning: 's' may be used uninitialized in this function [-Wmaybe-uninitialized]
72 | ans[0] = s;
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
708 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
708 KB |
Wrong Answer [5] |
| 2 |
Halted |
0 ms |
0 KB |
- |
