제출 #933628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933628		vjudge1	Speedrun (RMI21_speedrun)	C++17	0 / 100	139 ms	1900 KiB

speedrun

#include<bits/stdc++.h>
#include "speedrun.h"
using namespace std;

using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>;

#define sz(a) (int)a.size()
#define pb push_back
#define ins insert
#define f first 
#define s second

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define F0R(i,a) FOR(i,0,a)
#define each(i,a) for(auto i:a)
/*
const int ini = 3;
int curr = 3;
bool mem[1000][1000];

void setHintLen(int l){};
void setHint(int i,int j,bool b){
	mem[i][j]=b;
}
int getLength(){};
bool getHint(int j){
	return mem[curr][j];
}
bool goTo(int x){
	cout<<x<<endl;
	bool ans;
	cin>>ans;
	if(ans)curr=x;
	return ans;
}*/

vl ad1[1001];

void ass1(ll u,ll p){
	//cout<<"ass1 "<<u<<" "<<p<<endl;
	F0R(i,10)
	setHint(u,i+1,(p>>i)&1);
}
void ass2(ll u,ll p){
	//cout<<"ass2 "<<u<<" "<<p<<endl;
	F0R(i,10)
	setHint(u,i+11,(p>>i)&1);
}

void dfs1_1(ll u,ll p){
	ass1(u,p);
	each(v,ad1[u])
		if(v!=p)
			dfs1_1(v,u);
}
void dfs1_2(ll u,ll p,ll du,ll dp){
	if(sz(ad1[u])==1){
		ass1(u,du),ass2(u,dp);
	}
	else{
		each(v,ad1[u]){
			if(v!=p){
				ass2(u,v);
				dfs1_2(v,u,du,dp);
				du=u,dp=v;
			}
		}
	}
}

void assignHints(int subtask,int N,int A[],int B[]){
	F0R(i,N)ad1[A[i]].pb(B[i]),ad1[B[i]].pb(A[i]);
	setHintLen(20);
	dfs1_1(1,0);
	dfs1_2(1,0,0,0);
}
///////////////////////////////

ll rev1(){
	ll r=0;
	F0R(i,10)
		r+=(getHint(i+1)<<i);
	///cout<<"rev1 "<<curr<<" "<<r<<endl;
	return r;
}
ll rev2(){
	ll r=0;
	F0R(i,10)
		r+=(getHint(i+11)<<i);
	//cout<<"rev2 "<<curr<<" "<<r<<endl;
	return r;
}

pl dfs2(ll u,ll p){
	ll val=rev2();
	pl ret;
	bool r=goTo(val);
	if(r){
		ret=dfs2(val,u);
		while(u==ret.f){
			goTo(ret.s);
			ret=dfs2(ret.s,u);
		}
		goTo(p);
		return ret;
	}else{
		ret={rev1(),val};
		goTo(p);
		return ret;
	}
}

void speedrun(int subtask,int N,int start){
	if(start!=1){
		ll val=rev1();
		bool r=goTo(val);
		if(!r){
			FOR(i,1,N+1){
				if(i!=val)r=goTo(i);
				if(r)break;
			}
		}
		while(val!=1)val=rev1(),goTo(val);
	}
	dfs2(1,0);
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 8
• Subtask 3: 0 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 40