Submission #212960

#	Time	Username	Problem	Language	Result	Execution time	Memory
212960		ryansee	Stray Cat (JOI20_stray)	C++14	100 / 100	358 ms	16780 KiB

Anthony

#include "Anthony.h"
#include "bits/stdc++.h"
using namespace std;

namespace {

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
// inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
// string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (20006)
vector<int> v[MAXN];
// RRBRBB
int colour[] = {0,0,1,0,1,1};
}  // namespace

vector<int> Mark(int n, int m, int A, int B,vector<int> U, vector<int> vv) {
	FOR(i,0,m-1){
		v[U[i]].eb(vv[i]), v[vv[i]].eb(U[i]);
	}
	if(A>2){
		vector<int> C(m),dist(n,-1);
		queue <ll> q;
		q.ph(0);
		dist[0]=0;
		while(q.size()){
			ll x=q.front(); q.pop();
			for(auto i:v[x]) if(dist[i]==-1) {
				dist[i]=dist[x]+1;
				q.ph(i);
			}
		}
		FOR(i,0,m-1){
			ll a=U[i], b=vv[i];
			if(dist[a] > dist[b]) swap(a,b);
			if(dist[a]==dist[b]) C[i]=dist[a]+1, C[i]%=3;
			else assert(dist[b]==dist[a]+1), C[i]=dist[b]%3;	
		}
		return C;
	}
	vector<int> C(m);
	vector<bool> V(n);
	vector<int> depth(n,0);
	function<void(ll,ll,ll)>dfs=[&](ll x,ll p,ll c){
		V[x]=colour[c];
		if(siz(v[x])-(p!=x) == 1){ // line
			if(v[x][0]==p) v[x].erase(v[x].begin());
			depth[v[x][0]]=depth[x]+1, dfs(v[x][0], x, (c+1)%6);
		}else{
			for(auto i:v[x])if(i^p){
				depth[i]=depth[x]+1, dfs(i,x,(V[x]==1?0:2));
			}
		}
	};
	dfs(0,0,0);
	FOR(i,0,m-1){ll a=U[i],b=vv[i];
		if(depth[a]<depth[b])swap(a,b);
		C[i]=V[a];
		cerr<<a<<' '<<b<<' '<<C[i]<<'\n';
	}
	return C;
}

Catherine

#include "Catherine.h"
#include "bits/stdc++.h"
using namespace std;

namespace {

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define ph push
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
// inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
// string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (20006)
ll A, B, start, lst=-1, gg=0, bckt=0;
vector<int> C;
map<vector<int>,bool> mp;
int colour[] = {0,0,1,0,1,1};
}  // namespace

void Init(int A, int B) {
	::C.clear(), ::mp.clear();
	::start=1, ::A=A, ::B=B;
	FOR(i,0,5) {
		vector<int> tmp;
		DEC(j,i,i-4) tmp.pb(colour[(j+6)%6]);
		mp[tmp]=1;
	}
}

int Move(vector<int> y) {
	if(A>2){
		ll nz=0;
		FOR(i,0,A-1) if(y[i]) nz ++;
		assert(nz <= 2);
		if(nz == 1) {
			return y[0] ? 0 : (y[1] ? 1 : 2);
		}
		if(y[0] && y[1]) return 0;
		if(y[1] && y[2]) return 1;
		if(y[2] && y[0]) return 2;
		assert(0);
	}
	int deg=accumulate(all(y), 0ll);
	if(start){
		start=0;
		assert(deg>0);
		if(deg==1){
			lst=y[0]?0:1;
			return lst;
		}else if(deg==2){
			gg=1;
			FOR(i,0,1) FOR(j,1,y[i]) C.pb(i);
			return lst=(y[1]?1:0);
		}else{ // >2
			assert(y[0]==1||y[1]==1); 
			return lst = (y[0]==1 ? 0 : 1);
		}
	}
	if(bckt) {
		if(siz(C)==1){
			gg=0, bckt=0, assert(deg==1);
			C.clear();
			return lst = (y[0]?0:1);
		}else{
			cbr;
			C.pop_back();
			assert((y[0]==1)+(y[1]==1)==1);
			return lst=(y[0]?0:1);
		}
	}
	if(gg) {// rmbr +1 to deg
		if(deg==0){
			cerr<<"no\n";
			C.pop_back();bckt=1;
			return lst=-1;
		}else if(deg==1){
			if(y[0]) C.pb(0); else C.pb(1);
			if(siz(C)<5){
				return lst=(y[0]?0:1);
			}else{assert(siz(C)==5); // pop 2
				for(auto i:C) cerr<<i<<' '; cerr<<'\n';
				if(mp[C]){// correct
					gg=0;
					C.clear();
					return lst=(y[0]?0:1);
				}else{
					bckt=1;
					C.pop_back(), C.pop_back();
					cerr<<"flip\n";
					return lst=-1;
				}
			}
		}else { // deg + 1 > 2
			if(y[0]==0||y[1]==0){// wrong
				bckt=1;
				C.pop_back();
				cerr<<y[0]<<' '<<y[1]<<'\n';
				return lst=-1;
			}else{
				gg=0;
				C.clear();
			}
		}
	}
	assert(lst!=-1);
	ll zero=y[0],one=y[1];
	lst ? ++ one : ++ zero;
	if(one==1&&zero==1){
		lst ^= 1; return lst;
	}
	if(min(one,zero)==0){
		return lst;
	}
	if(zero == 1 || one == 1); else assert(0);
	if(zero==1) { return lst=0; }
	else { return lst=1; }
}
/*
7 6 2 6 4
0 2
0 4
1 2
1 3
1 5
4 6
*/ 

Compilation message (stderr)

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:100:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto i:C) cerr<<i<<' '; cerr<<'\n';
     ^~~
Catherine.cpp:100:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(auto i:C) cerr<<i<<' '; cerr<<'\n';
                                 ^~~~

• 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