Submission #565997

#	Time	Username	Problem	Language	Result	Execution time	Memory
565997		errorgorn	Stray Cat (JOI20_stray)	C++17	100 / 100	58 ms	16732 KiB

Anthony

#include "Anthony.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {
	bool st;
	int n,m;
	vector<int> al[20005];
	
	int w[20005];
	queue<int> q;
	
	int d[20005];
	int pat[20005];
	int col[20005];
	
	void dfs(int i,int p){
		int child=0;
		for (auto it:al[i]){
			if (it==p) continue;
			child++;
		}
		
		for (auto it:al[i]){
			if (it==p) continue;
			
			if (child>1){
				pat[it]=col[it]=col[i]^1;
			}
			else{
				pat[it]=(pat[i]+1)%7;
				
				vector<int> C={0,1,0,0,1,1,1};
				col[it]=C[pat[it]];
			}
			
			d[it]=d[i]+1;
			dfs(it,i);
		}
	}
}

vector<signed> Mark(signed N, signed M, signed A, signed B,
                      vector<signed> U, vector<signed> V) {
						  
	
	st=(A>=3);
	n=N,m=M;
	rep(x,0,m){
		al[U[x]].pub(V[x]);
		al[V[x]].pub(U[x]);
	}
	
	if (st){
		memset(w,-1,sizeof(w));
		q.push(0);
		w[0]=0;
		
		while (!q.empty()){
			int u=q.front(); q.pop();
			for (auto it:al[u]) if (w[it]==-1){
				w[it]=w[u]+1;
				q.push(it);
			}
		}
		
		vector<signed> res;
		rep(x,0,m){
			res.pub(min(w[U[x]],w[V[x]])%3);
			//cout<<res.back()<<" "<<U[x]<<" "<<V[x]<<endl;
		}
		return res;
	}
	else{
		dfs(0,-1);
		
		vector<signed> res;
		rep(x,0,m){
			if (d[U[x]]>d[V[x]]) swap(U[x],V[x]);
			res.pub(col[V[x]]);
		}
		
		//for (auto it:res) cout<<it<<" "; cout<<endl;
		return res;
	}
}

Catherine

#include "Catherine.h"

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

#define int long long
#define ii pair<int,int>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

namespace {
	bool st;
	int PREV=-1;
	
	set<string> good={
		"01001",
		"10011",
		"00111",
		"01110",
		"11101",
		"11010",
		"10100"
	};
	
	bool dir=false;
	string s="";
}

void Init(signed A, signed B) {
	st=(A>=3);
}

signed Move(vector<signed> y) {
	if (st){
		vector<int> v;
		rep(x,0,3) if (y[x] || PREV==x) v.pub(x);
		sort(all(v));
		
		if (sz(v)==1){
			return PREV=v[0];
		}
		else if (v[1]==1){
			return PREV=0;
		}
		else if (v[0]==1){
			return PREV=1;
		}
		else{
			return PREV=2;
		}
	}
	else{
		int tot=(PREV!=-1);
		rep(x,0,2) tot+=y[x];
		
		if (tot>=3){
			dir=true;
			if (PREV!=-1) y[PREV]++;
			rep(x,0,2) if (y[x]==1){
				if (PREV!=x) return PREV=x;
				else return -1;
			}
		}
		else if (tot==1){
			dir=true;
			if (PREV!=-1) y[PREV]++;
			rep(x,0,2) if (y[x]==1){
				if (PREV!=x) return PREV=x;
				else return -1;
			}
		}
		else if (dir){
			rep(x,0,2) if (y[x]==1) return PREV=x;
		}
		else{
			if (s==""){
				rep(x,2,0) rep(z,0,y[x]) s+='0'+x;
				//cout<<s<<endl;
				rep(x,0,2) if (y[x]) return PREV=x;
			}
			else{
				rep(x,0,2) rep(z,0,y[x]) s+='0'+x;
				//cout<<s<<endl;
				if (sz(s)==5){
					dir=true;
					if (!good.count(s)){
						rep(x,0,2) if (y[x]==1) return PREV=x;
					}
					else{
						return -1; //PREV is same
					}
				}
				else{
					rep(x,0,2) if (y[x]) return PREV=x;
				}
			}
		}
		
	}
}

Compilation message (stderr)

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

• 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