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<i_am_noob_orz>
#include<bits/stdc++.h>
#include "chameleon.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
//#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
if(b==0)return 1;
if(b==1)return(a%mod);
int tem=po(a,b/2);
if(b&1)return(((tem*tem)%mod)*a)%mod;
else return(tem*tem)%mod;
}
int GCD(int a,int b){
int x=0;
int ra,rb;
while(a&&b){
if(((a&1)==0)&&((b&1)==0)){
a>>=1,b>>=1,x++;
}
else if((a^b)&1){
if(a&1)b>>=1;
else a>>=1;
}
else{
ra=abs(a-b),rb=min(a,b);
a=ra,b=rb;
}
}
return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
#ifdef LOCAL
int Query(vector<int> &v){for(int i:v)cout<<i<<" ";cout<<endl;return 0;}
void Answer(int x,int y){}
#endif
int n,gr[1005];
bool vis[1005];
vector<int> g[1005],tv,rg[1005];
void dfs(int p,int ty){
vis[p]=1;
gr[p]=ty;
for(int u:g[p]){
if(!vis[u])dfs(u,1-ty);
}
}
void fd_ed(int x){
Fi(ti,3){
if(sz(tv)==0)return;
tv.pb(x+1);
int re=Query(tv);
int y;
if(re!=sz(tv)){
//assert(re==sz(tv)-1);
vector<int> ttv;
F(sz(tv)-1)ttv.pb(tv[i]);
while(sz(ttv)>1){
int mi=(sz(ttv)/2);
vector<int> tttv;
F(mi)tttv.pb(ttv[i]);
tttv.pb(x+1);
int re=Query(tttv);
if(re!=sz(tttv)){
tttv.pop_back();
}
else{
tttv.clear();
for(int i=mi;i<sz(ttv);i++)tttv.pb(ttv[i]);
}
swap(tttv,ttv);
}
assert(sz(ttv)==1);
g[x].pb(ttv[0]-1);
g[ttv[0]-1].pb(x);
y=ttv[0];
}
else{
return;
}
tv.pop_back();
vector<int> ttv;
for(int i:tv){
if(i!=y)ttv.pb(i);
}
swap(tv,ttv);
}
}
void Solve(int N){
n=N*2;
F(n){
memres(vis);
Fi(j,i){
if(!vis[j])dfs(j,0);
}
tv.clear();
Fi(j,i){
if(gr[j]==0)tv.pb(j+1);
}
if(sz(tv)!=0){
fd_ed(i);
}
tv.clear();
Fi(j,i){
if(gr[j]==1)tv.pb(j+1);
}
if(sz(tv)!=0){
fd_ed(i);
}
}
F(n){
if(sz(g[i])==3){
vector<int> v1,v2;
v1.pb(i+1);v1.pb(g[i][0]+1);v1.pb(g[i][1]+1);
v2.pb(i+1);v2.pb(g[i][0]+1);v2.pb(g[i][2]+1);
if(Query(v1)==1){
rg[i].pb(g[i][2]);
rg[g[i][2]].pb(i);
}
else if(Query(v2)==1){
rg[i].pb({g[i][1]});
rg[g[i][1]].pb(i);
}
else{
rg[i].pb({g[i][0]});
rg[g[i][0]].pb(i);
}
}
else assert(sz(g[i])==1);
}
memres(vis);
F(n){
if(vis[i])continue;
if(sz(g[i])==1){
Answer(i+1,g[i][0]+1);
vis[i]=1;
vis[g[i][0]]=1;
continue;
}
if(g[i][0]!=rg[i][0]&&g[i][0]!=rg[i][1]){
Answer(i+1,g[i][0]+1);
vis[i]=1;
vis[g[i][0]]=1;
}
else if(g[i][1]!=rg[i][0]&&g[i][1]!=rg[i][1]){
Answer(i+1,g[i][1]+1);
vis[i]=1;
vis[g[i][1]]=1;
}
else{
Answer(i+1,g[i][2]+1);
vis[i]=1;
vis[g[i][2]]=1;
}
}
}
#ifdef LOCAL
signed main(){
IOS();
Solve(10);
return 0;
}
#endif
# | 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... |