Submission #1139780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139780		Zbyszek99	Stray Cat (JOI20_stray)	C++20	29 / 100	46 ms	14408 KiB

Anthony

#include "Anthony.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vector<int> seq = {1,0,1,1,0,0};
set<int> pos_segs = {13,6,19,9,20,26};
vector<pii> graph[20'001];
vi ans;
bool is_tree;
vi moves;
int cur_seg = 0;
bool odw[20'001];
int dist[20'001];

void dfs_color(int v, int pop, int path_ind, int pop_color)
{
	forall(it,graph[v])
	{
		if(it.ff == pop) continue;
		if(path_ind != -1)
		{
			ans[it.ss] = seq[path_ind];
		}
		else
		{
			ans[it.ss] = pop_color^1;
		}
		if(siz(graph[it.ff]) <= 2)
		{
			if(path_ind != -1)
			{
				dfs_color(it.ff,v,(path_ind+1) % siz(seq),ans[it.ss]);
			}
			else
			{
				if(pop_color == 0)
				{
					dfs_color(it.ff,v,1,ans[it.ss]);
				}
				else
				{
					dfs_color(it.ff,v,2,ans[it.ss]);
				}
			}
		}
		else
		{
			dfs_color(it.ff,v,-1,ans[it.ss]);
		}
	}
}

vector<int> Mark(int n, int m, int A, int B, vector<int> _U, vector<int> _V) 
{
	ans.resize(m);
	rep(i,m)
	{
		graph[_U[i]].pb({_V[i],i});
		graph[_V[i]].pb({_U[i],i});
	}
	if(B != 0)
	{
		if(siz(graph[0]) > 1)
		{
			dfs_color(0,0,-1,0);
		}
		else
		{
			dfs_color(0,0,0,0);
		}
	}
	else
	{
		queue<pii> q;
		q.push({0,0});
		while(!q.empty())
		{
			pii t = q.front();
			q.pop();
			if(odw[t.ff]) continue;
			dist[t.ff] = t.ss;
			odw[t.ff] = 1;
			forall(it,graph[t.ff])
			{
				q.push({it.ff,t.ss+1});
			} 
		}
		//rep(i,n) cout << dist[i] << " " << i << " dist\n";
		rep(i,m)
		{
			if(dist[_U[i]] < dist[_V[i]]) swap(_U[i],_V[i]);
			ans[i] = dist[_V[i]] % 3;
		}
	}
	//rep(i,m)
	//{
	//	cout << _U[i] << " " << _V[i] << " " << ans[i] << " tree\n";
	//}
	return ans;
}

void Init(int A, int B) 
{
	if(B != 0) is_tree =1;
	else is_tree = 0;
}

int Move(vector<int> y) 
{
	//cout << "ruch\n";
	//cout << y[0] << " " << y[1] << " y\n";
	if(is_tree)
	{
		if(siz(moves) == 0)
		{
			int s = y[0] + y[1];
			if(s > 2)
			{
				if(y[0] == 1)
				{
					moves.pb(0);
					return 0;
				}
				else
				{
					moves.pb(1);
					return 1;
				}
				cur_seg = -1;
			}
			else if(s == 1)
			{
				if(y[0] == 1)
				{
					moves.pb(0);
					return 0;
				}
				else
				{
					moves.pb(1);
					return 1;
				}
				cur_seg = -1;
			}
			else
			{	
				if(y[0] >= 1)
				{
					y[0]--;
				}
				else
				{
					cur_seg += (1 << 0);
				}
				if(y[0] != 0)
				{
					moves.pb(0);
					return 0;
				}
				else
				{
					cur_seg += (1 << 1);
					moves.pb(1);
					return 1;
				}
			}	
		}
		else
		{
			//cout << cur_seg << " cur_seg\n";
			if(cur_seg == -1)
			{
				int s = y[0]+y[1];
				if(s == 1)
				{
					if(y[0] == 1)
					{
						moves.pb(0);
						return 0;
					}
					else
					{
						moves.pb(1);
						return 1;
					}
				}
				int m = moves.back()^1;
				moves.pb(m);
                if(y[m] != 0)
                {
				    return m;
                }
                else return m^1;
			}
			else 
			{
				int s = y[0] + y[1];
				if(s == 1)
				{
					if(y[1] == 1)
					{
						cur_seg += (1 << (siz(moves)+1));
					}
					if(siz(moves) == 3)
					{
					//	cout << cur_seg << " move3_seg\n";
						if(pos_segs.find(cur_seg) == pos_segs.end())
						{
							cur_seg = -1;
							if(y[0] == 1)
							{
								moves.pb(0);
								return 0;
							}
							else
							{
								moves.pb(1);
								return 1;
							}
						}
						else
						{
							cur_seg = -1;
							return -1;
						}
					}
					if(y[1] == 1)
					{
						moves.pb(1);
						return 1;
					}
					else
					{
						moves.pb(0);
						return 0;
					}
				}
				else
				{
					int m = moves.back();
					cur_seg = -1;
					if(y[m^1] == 1)
					{
						moves.pb(m^1);
						return m^1;
					}
					else
					{
						return -1;
					}
				}
			}
		}
	}
	else
	{
		set<int> pom;
		rep(i,3) if(y[i] != 0) pom.insert(i);
		if(siz(pom) == 1) return *pom.begin();
		if(y[0] == 0) return 1;
		if(y[1] == 0) return 2;
		if(y[2] == 0) return 0;
	}
}

Catherine

#include "Catherine.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vector<int> seq = {1,0,1,1,0,0};
set<int> pos_segs = {13,6,19,9,20,26};
vector<pii> graph[20'001];
vi ans;
bool is_tree;
vi moves;
int cur_seg = 0;
bool odw[20'001];
int dist[20'001];

void dfs_color(int v, int pop, int path_ind, int pop_color)
{
	forall(it,graph[v])
	{
		if(it.ff == pop) continue;
		if(path_ind != -1)
		{
			ans[it.ss] = seq[path_ind];
		}
		else
		{
			ans[it.ss] = pop_color^1;
		}
		if(siz(graph[it.ff]) <= 2)
		{
			if(path_ind != -1)
			{
				dfs_color(it.ff,v,(path_ind+1) % siz(seq),ans[it.ss]);
			}
			else
			{
				if(pop_color == 0)
				{
					dfs_color(it.ff,v,1,ans[it.ss]);
				}
				else
				{
					dfs_color(it.ff,v,2,ans[it.ss]);
				}
			}
		}
		else
		{
			dfs_color(it.ff,v,-1,ans[it.ss]);
		}
	}
}

vector<int> Mark(int n, int m, int A, int B, vector<int> _U, vector<int> _V) 
{
	ans.resize(m);
	rep(i,m)
	{
		graph[_U[i]].pb({_V[i],i});
		graph[_V[i]].pb({_U[i],i});
	}
	if(B != 0)
	{
		if(siz(graph[0]) > 1)
		{
			dfs_color(0,0,-1,0);
		}
		else
		{
			dfs_color(0,0,0,0);
		}
	}
	else
	{
		queue<pii> q;
		q.push({0,0});
		while(!q.empty())
		{
			pii t = q.front();
			q.pop();
			if(odw[t.ff]) continue;
			dist[t.ff] = t.ss;
			odw[t.ff] = 1;
			forall(it,graph[t.ff])
			{
				q.push({it.ff,t.ss+1});
			} 
		}
		//rep(i,n) cout << dist[i] << " " << i << " dist\n";
		rep(i,m)
		{
			if(dist[_U[i]] < dist[_V[i]]) swap(_U[i],_V[i]);
			ans[i] = dist[_V[i]] % 3;
		}
	}
	//rep(i,m)
	//{
	//	cout << _U[i] << " " << _V[i] << " " << ans[i] << " tree\n";
	//}
	return ans;
}

void Init(int A, int B) 
{
	if(B != 0) is_tree =1;
	else is_tree = 0;
}

int Move(vector<int> y) 
{
	//cout << "ruch\n";
	//cout << y[0] << " " << y[1] << " y\n";
	if(is_tree)
	{
		if(siz(moves) == 0)
		{
			int s = y[0] + y[1];
			if(s > 2)
			{
				if(y[0] == 1)
				{
					moves.pb(0);
					return 0;
				}
				else
				{
					moves.pb(1);
					return 1;
				}
				cur_seg = -1;
			}
			else if(s == 1)
			{
				if(y[0] == 1)
				{
					moves.pb(0);
					return 0;
				}
				else
				{
					moves.pb(1);
					return 1;
				}
				cur_seg = -1;
			}
			else
			{	
				if(y[0] >= 1)
				{
					y[0]--;
				}
				else
				{
					cur_seg += (1 << 0);
				}
				if(y[0] != 0)
				{
					moves.pb(0);
					return 0;
				}
				else
				{
					cur_seg += (1 << 1);
					moves.pb(1);
					return 1;
				}
			}	
		}
		else
		{
			//cout << cur_seg << " cur_seg\n";
			if(cur_seg == -1)
			{
				int s = y[0]+y[1];
				if(s == 1)
				{
					if(y[0] == 1)
					{
						moves.pb(0);
						return 0;
					}
					else
					{
						moves.pb(1);
						return 1;
					}
				}
				int m = moves.back()^1;
				moves.pb(m);
                if(y[m] != 0)
                {
				    return m;
                }
                else return m^1;
			}
			else 
			{
				int s = y[0] + y[1];
				if(s == 1)
				{
					if(y[1] == 1)
					{
						cur_seg += (1 << (siz(moves)+1));
					}
					if(siz(moves) == 3)
					{
					//	cout << cur_seg << " move3_seg\n";
						if(pos_segs.find(cur_seg) == pos_segs.end())
						{
							cur_seg = -1;
							if(y[0] == 1)
							{
								moves.pb(0);
								return 0;
							}
							else
							{
								moves.pb(1);
								return 1;
							}
						}
						else
						{
							cur_seg = -1;
							return -1;
						}
					}
					if(y[1] == 1)
					{
						moves.pb(1);
						return 1;
					}
					else
					{
						moves.pb(0);
						return 0;
					}
				}
				else
				{
					int m = moves.back();
					cur_seg = -1;
					if(y[m^1] == 1)
					{
						moves.pb(m^1);
						return m^1;
					}
					else
					{
						return -1;
					}
				}
			}
		}
	}
	else
	{
		set<int> pom;
		rep(i,3) if(y[i] != 0) pom.insert(i);
		if(siz(pom) == 1) return *pom.begin();
		if(y[0] == 0) return 1;
		if(y[1] == 0) return 2;
		if(y[2] == 0) return 0;
	}
}

Compilation message (stderr)

# 1번째 컴파일 단계

Anthony.cpp: In function 'int Move(std::vector<int>)':
Anthony.cpp:290:1: warning: control reaches end of non-void function [-Wreturn-type]
  290 | }
      | ^

# 2번째 컴파일 단계

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:290:1: warning: control reaches end of non-void function [-Wreturn-type]
  290 | }
      | ^

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