Submission #212281

#	Time	Username	Problem	Language	Result	Execution time	Memory
212281		Evirir	Stray Cat (JOI20_stray)	C++17	100 / 100	103 ms	22400 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF ll(1e18)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 200005

namespace ant{
string s="010110";
bool DEBUG=0;
int n,m;
vii adj[MAXN];
}
using namespace ant;

vector<int> ans;

bool vst[MAXN];
int dep[MAXN];

void bfs1()
{
	mset(vst,0); mset(dep,0);
	queue<int> q;
	q.push(0);
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(ii tmp: adj[u]){
			int v=tmp.F;
			if(vst[v]) continue;
			
			dep[v]=dep[u]+1;
			vst[v]=1;
			q.push(v);
		}
	}
}

void bfs()
{
	mset(vst,0);
	queue<ii> q;
	q.push({0,0});
	
	vst[0]=1;
	while(!q.empty()){
		int u=q.front().F, c=q.front().S; q.pop();
		
		for(ii tmp: adj[u]){
			int v=tmp.F, id=tmp.S;
			
			if(vst[v]){
				if(ans[id]==-1){
					if(dep[u]>dep[v]) ans[id]=(c-1)%3;
					else ans[id]=c;
					
					if(DEBUG) cout<<"c="<<c<<" Edge "<<u<<"-"<<v<<": "<<ans[id]<<" dep[u]="<<dep[u]<<" dep[v]="<<dep[v]<<" u="<<u<<" v="<<v<<'\n';
				}
			}
			else{
				if(ans[id]==-1){
					ans[id]=c;
					if(DEBUG) cout<<"Edge "<<u<<"-"<<v<<": "<<ans[id]<<'\n';
				}
				vst[v]=1;
				q.push({v,(c+1)%3});
			}
		}
	}
}

void dfs(int u,int p,int c,int pos)
{
	if(adj[u].size()==2)
	{
		for(ii tmp: adj[u]){
			int v=tmp.F, id=tmp.S;
			if(v==p) continue;
			
			ans[id]=s[pos]-'0';
			dfs(v,u,ans[id]^1,(pos+1)%6);
		}
		
		return;
	}
	
	for(ii tmp: adj[u]){
		int v=tmp.F, id=tmp.S;
		if(v==p) continue;
		
		ans[id]=c;
		dfs(v,u,c^1,c+1);
	}
}

vector<int> Mark(int n, int m, int A, int B, vector<int> U, vector<int> V)
{
	ans.resize(m,-1);
	mset(vst,0);
	
	forn(i,0,m){
		adj[U[i]].pb({V[i],i});
		adj[V[i]].pb({U[i],i});
	}
	
	if(A>=3){
		bfs1(); bfs();
	}
	else dfs(0,-1,0,0);
	
	return ans;
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=a;i<b;i++)
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define INF ll(1e18)
#define MOD 998244353
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#define MAXN 200005

namespace cat{
int A,B;
bool DEBUG=0;
int Prev=-1;
string s;
}
using namespace cat;

int mode=0;
string banarr[4]={"0010","0101","01100","1100"};
unordered_set<string> ban;

void Init(int _A, int _B)
{
	A=_A; B=_B; mode=0; Prev=-1; s="";
	ban.clear(); ban.insert(banarr,banarr+4);
}

int cmp(int a,int b){
	if(a>b) swap(a,b);
	if(a==0 && b==2) return 2;
	return a;
}

int Move1(vector<int> &v1)
{
	vector<int> v;
	forn(i,0,3) if(v1[i]) v.pb(i);
	
	if(DEBUG){
		cout<<"Possible moves: ";
		forn(i,0,v.size()) cout<<v[i]<<" ";
		cout<<'\n';
	}
	
	assert(v.size()==1 || v.size()==2);
	
	if(v.size()==1) return v[0];
	return cmp(v[0],v[1]);
}

int Move2(vector<int> &v)
{	
	//first 3 steps, dunno direction
	if(!mode)
	{
		//first step
		if(Prev==-1)
		{
			//leaf node
			if(v[0]+v[1]==1)
			{
				if(DEBUG) cout<<"1st step: leaf node\n";
				
				mode=1;
				Prev=(v[0]>0?0:1);
				return Prev;
			}
			
			//non-line
			else if(v[0]+v[1]>=3)
			{
				if(DEBUG) cout<<"1st step: non-line\n";
				assert(v[0]==1 || v[1]==1);
				
				mode=1;
				if(v[0]==1){
					Prev=0;
					return Prev;
				}
				else{
					Prev=1;
					return Prev;
				}
			}
			
			//line graph
			else
			{
				if(DEBUG) cout<<"1st step: line graph\n";
				
				if(v[0]==2 && v[1]==0){
					s+="00";
					Prev=0;
					return 0;
				}
				if(v[0]==1 && v[1]==1){
					s+="01";
					Prev=1;
					return 1;
				}
				if(v[0]==0 && v[1]==2){
					s+="11";
					Prev=1;
					return 1;
				}
			}
			
			cout<<"First step fail\n";
			assert(0);
		}
		//first step end
		
		//second/third step
		else
		{
			//leaf node
			if(v[0]+v[1]==0)
			{
				if(DEBUG) cout<<"2/3 step: leaf\n";
				
				mode=1;
				Prev=s.back()-'0';
				s.pop_back();
				return -1;
			}
			
			//non-line: added v
			else if(v[0]+v[1]>=2)
			{
				if(DEBUG) cout<<"2/3 step: non-line\n";
				
				if(Prev==0) v[0]++;
				else v[1]++;
				assert(v[0]==1 || v[1]==1);
				
				mode=1;
				if(v[0]==1){
					if(Prev==0) return -1;
					Prev=0;
					return Prev;
				}
				else{
					if(Prev==1) return -1;
					Prev=1;
					return Prev;
				}
			}
			
			//line graph
			else //v[0]==1 || v[1]==1
			{
				if(DEBUG) cout<<"2/3 step: line\n";
				
				//third step, decide
				if(s.size()==4){
					mode=1;
					
					if(DEBUG) cout<<"s="<<s<<'\n';
					
					if(ban.find(s)!=ban.end()){
						Prev=s.back()-'0';
						s.pop_back();
						return -1;
					}
					else{
						if(v[0]) s+='0';
						else s+='1';
						if(DEBUG) cout<<"s="<<s<<'\n';
						
						if(ban.find(s)!=ban.end()){
							//Prev remains
							s.pop_back();
							return -1;
						}
						else{
							Prev=(v[0]?0:1);
							return Prev;
						}
					}
				}
				
				//second step
				if(v[0]==1 && v[1]==0){
					s+="0";
					Prev=0;
					return 0;
				}
				if(v[0]==0 && v[1]==1){
					s+="1";
					Prev=1;
					return 1;
				}
			}
			
			cout<<"Second/third step fail\n";
			assert(0);
		}
		//second/third step end
	}
	
	//direction confirmed
	else
	{		
		assert(v[0]+v[1]!=0);
		
		//line graph
		if(v[0]+v[1]==1)
		{
			if(v[0]){
				Prev=0; return 0;
			}
			else{
				Prev=1; return 1;
			}
		}
		
		//non-line
		else
		{
			v[Prev]++;
			if(DEBUG) cout<<"Prev="<<Prev<<" v[0]="<<v[0]<<" v[1]="<<v[1]<<'\n';
			if(v[0]==1){
				Prev=0; return 0;
			}
			else{
				Prev=1; return 1;
			}
		}
		
		assert(0);
		return 222;
	}
	
	return 333;
}

int Move(vector<int> v)
{
	if(A>=3) return Move1(v);
	return Move2(v);
}

Compilation message (stderr)

Catherine.cpp: In function 'int Move1(std::vector<int>&)':
Catherine.cpp:11:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forn(i,a,b) for(int i=a;i<b;i++)
Catherine.cpp:61:8:
   forn(i,0,v.size()) cout<<v[i]<<" ";
        ~~~~~~~~~~~~               
Catherine.cpp:61:3: note: in expansion of macro 'forn'
   forn(i,0,v.size()) cout<<v[i]<<" ";
   ^~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 71 / 71
• Subtask 7: 9 / 9