This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "icc.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
template<int SZ> struct DSU {
int par[SZ], sz[SZ];
DSU() {
F0R(i,SZ) par[i] = i, sz[i] = 1;
}
int get(int x) { // path compression
if (par[x] != x) par[x] = get(par[x]);
return par[x];
}
bool unite(int x, int y) { // union-by-rank
x = get(x), y = get(y);
if (x == y) return 0;
if (sz[x] < sz[y]) swap(x,y);
sz[x] += sz[y], par[y] = x;
return 1;
}
};
DSU<101> D;
int N;
/*pi des;
int query(int size_a, int size_b, int a[], int b[]) {
F0R(i,size_a) cout << a[i] << " ";
cout << "| ";
F0R(i,size_b) cout << b[i] << " ";
cout << "|\n";
F0R(i,size_a) F0R(j,size_b) {
if (a[i] == des.f && b[j] == des.s) return 1;
if (a[i] == des.s && b[j] == des.f) return 1;
}
return 0;
}*/
bool QUERY(vi a, vi b) {
int A[sz(a)]; F0R(i,sz(a)) A[i] = a[i];
int B[sz(b)]; F0R(i,sz(b)) B[i] = b[i];
return query(sz(a),sz(b),A,B);
}
void ad(vi& a, vi b) { for (int i: b) a.pb(i); }
/*void setRoad(int a, int b) {
cout << "AH " << a << " " << b << "\n";
if (mp(a,b) == mp(3,1)) des = {4,2};
else exit(0);
}*/
void bipartite(vi x, vi y) {
while (1) {
if (sz(x) < sz(y)) swap(x,y);
if (sz(x) == 1) {
D.unite(x[0],y[0]);
setRoad(x[0],y[0]);
return;
}
vi X = vi(x.begin(),x.begin()+sz(x)/2);
if (QUERY(X,y)) x = X;
else x = vi(x.begin()+sz(x)/2,x.end());
}
}
void getBit(vector<vi> V) {
int cur = 1, xo = 0;
while (cur < sz(V)) {
vi a,b;
F0R(i,sz(V)) {
if (i&cur) ad(a,V[i]);
else ad(b,V[i]);
}
if (QUERY(a,b)) xo ^= cur;
cur *= 2;
}
vector<pair<vi,vi>> posiGroup;
F0R(i,sz(V)) if ((i^xo) > i && (i^xo) < sz(V)) posiGroup.pb({V[i],V[i^xo]});
while (sz(posiGroup) > 1) {
vi a,b;
F0R(i,sz(posiGroup)/2) {
ad(a,posiGroup[i].f);
ad(b,posiGroup[i].s);
}
if (QUERY(a,b)) {
posiGroup = vector<pair<vi,vi>>(posiGroup.begin(),posiGroup.begin()+sz(posiGroup)/2);
} else {
posiGroup = vector<pair<vi,vi>>(posiGroup.begin()+sz(posiGroup)/2,posiGroup.end());
}
}
bipartite(posiGroup[0].f,posiGroup[0].s);
}
void solve() {
vi v[101];
FOR(i,1,N+1) v[D.get(i)].pb(i);
vector<vi> V;
FOR(i,1,N+1) if (sz(v[i])) V.pb(v[i]);
getBit(V);
}
void run(int n) {
N = n;
F0R(i,N-1) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |