#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include "chameleon.h"
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 1000000007;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 1001;
int type[mxN], col[mxN], nxt[mxN];
/*void Answer(int a, int b) {
if(col[a]^col[b]) {
cout<<a<<" "<<b<<" you suck!\n";
exit(0);
}
}*/
int query(vector<int> &p) {
return Query(p);
/*set<int> colors;
vector<bool> here(mxN, 0);
for(int k: p) {
here[k] = 1;
}
for(int k: p) {
if(here[nxt[k]])colors.insert(col[nxt[k]]);
else colors.insert(col[k]);
}
return colors.size();*/
}
vector<int> getrange(int a, int b, vector<int> &c, int d) {
if(a > b)return {};
vector<int> q;
owo(i, a, b+1) {
q.senpai(c[i]);
}
int l = a;
int r = b;
q.senpai(d);
if(query(q) > b-a+1)return {};
while(l < r) {
q.clear();
int m = (l + r) >> 1;
owo(i, a, m+1) {
q.senpai(c[i]);
}
q.senpai(d);
if(query(q)<=m-a+1)r = m;
else l = m + 1;
}
vector<int> res = getrange(l+1, b, c, d);
res.senpai(c[l]);
return res;
}
vector<int> adj[mxN];
void bipartite(int n, vector<int> &l, vector<int> &r) {
vector<int> col(n+1, -1);
owo(i, 1, n+1) {
if(col[i]!=-1)continue;
queue<int> q;
q.push(i);
col[i] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int v: adj[u]) {
if(col[v]==-1) {
col[v] = col[u]^1;
q.push(v);
}
}
}
}
owo(i, 1, n+1) {
if(col[i])r.senpai(i);
else l.senpai(i);
}
}
void Solve(int n) {
vector<bool> done(2*n+1);
vector<int> point(2*n+1);
owo(i, 2, 2*n+1) {
vector<int> l, r;
bipartite(i-1, l, r);
vector<int> edges = getrange(0, l.size()-1, l, i);
for(int k: edges) {
adj[k].senpai(i);
adj[i].senpai(k);
}
edges = getrange(0, r.size()-1, r, i);
for(int k: edges) {
adj[k].senpai(i);
adj[i].senpai(k);
}
}
owo(i, 1, 2*n+1) {
if(done[i])continue;
if(adj[i].size()==1) {
Answer(i, adj[i][0]);
done[adj[i][0]] = 1;
}else if(adj[i].size()==3) {
vector<int> q = {i, adj[i][0], adj[i][1]};
if(query(q)==1) {
point[i] = adj[i][2];
}else {
q = {i, adj[i][0], adj[i][2]};
if(query(q)==1) {
point[i] = adj[i][1];
}else {
point[i] = adj[i][0];
}
}
}
}
owo(i, 1, 2*n+1) {
if(adj[i].size()==3) {
int o = point[i];
if(done[o])continue;
int sam = i^adj[o][0]^adj[o][1]^adj[o][2]^point[o];
Answer(o, sam);
done[o] = 1;
done[sam] = 1;
}
}
}
/*int main() {
//freopen("file.in", "r", stdin);
//freopen("file.out", "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
cin.tie(0)->sync_with_stdio(0);
int T = 1;
int n;
for(int tc = 1; tc <= T; tc++) {
cin>>n;
owo(i, 1, 2*n+1) {
cin>>type[i];
}
owo(i, 1, 2*n+1) {
cin>>col[i];
}
owo(i, 1, 2*n+1) {
cin>>nxt[i];
}
Solve(n);
}
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Correct |
50 ms |
376 KB |
Output is correct |
| 4 |
Correct |
49 ms |
328 KB |
Output is correct |
| 5 |
Correct |
50 ms |
384 KB |
Output is correct |
| 6 |
Correct |
51 ms |
392 KB |
Output is correct |
| 7 |
Correct |
58 ms |
392 KB |
Output is correct |
| 8 |
Correct |
51 ms |
492 KB |
Output is correct |
| 9 |
Correct |
50 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Runtime error |
64 ms |
648 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
328 KB |
Output is correct |
| 2 |
Correct |
0 ms |
328 KB |
Output is correct |
| 3 |
Correct |
50 ms |
376 KB |
Output is correct |
| 4 |
Correct |
49 ms |
328 KB |
Output is correct |
| 5 |
Correct |
50 ms |
384 KB |
Output is correct |
| 6 |
Correct |
51 ms |
392 KB |
Output is correct |
| 7 |
Correct |
58 ms |
392 KB |
Output is correct |
| 8 |
Correct |
51 ms |
492 KB |
Output is correct |
| 9 |
Correct |
50 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
328 KB |
Output is correct |
| 11 |
Correct |
0 ms |
328 KB |
Output is correct |
| 12 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 11 |
| 13 |
Halted |
0 ms |
0 KB |
- |
