oj.uz

Submission #212932

# Submission time Handle Problem Language Result Execution time Memory
212932 2020-03-24T14:44:41 Z ryansee Stray Cat (JOI20_stray) C++14
0 / 100
 398 ms 19552 KB 
#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]);
	}
	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?1: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;
}

#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;
	mp[{0,0,1,0,1,1}]=
		mp[{0,1,0,1,1,0}]=
			mp[{1,0,1,1,0,0}]=
				mp[{0,1,1,0,0,1}]=
					mp[{1,1,0,0,1,0}]=
						mp[{1,0,0,1,0,1}]=1;
}

int Move(vector<int> y) {
	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;
			}
		}
	}
	assert(lst!=-1);
	ll zero=y[0],one=y[1];
	lst ? ++ one : ++ zero;
	if(one==1&&zero==1){
		lst ^= 1; return lst;
	}
	if(max(zero,one)==2&&min(one,zero)==0){
		return lst;
	}
	if(zero == 1 || one == 1); else assert(0);
	if(zero==1) { assert(lst); return lst=0; }
	else { assert(lst==0); return lst=1; }
}
/*
7 6 2 6 4
0 2
0 4
1 2
1 3
1 5
4 6
*/

Compilation message

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:89:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto i:C) cerr<<i<<' '; cerr<<'\n';
     ^~~
Catherine.cpp:89: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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 17248 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 317 ms 15112 KB Output is correct
4 Correct 325 ms 19480 KB Output is correct
5 Incorrect 313 ms 19552 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 17248 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 317 ms 15112 KB Output is correct
4 Correct 325 ms 19480 KB Output is correct
5 Incorrect 313 ms 19552 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 14968 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 293 ms 12984 KB Output is correct
4 Correct 326 ms 17388 KB Output is correct
5 Incorrect 398 ms 17248 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 14968 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 293 ms 12984 KB Output is correct
4 Correct 326 ms 17388 KB Output is correct
5 Incorrect 398 ms 17248 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1792 KB Output is correct
2 Correct 11 ms 1536 KB Output is correct
3 Correct 22 ms 1792 KB Output is correct
4 Correct 22 ms 1792 KB Output is correct
5 Correct 19 ms 1792 KB Output is correct
6 Correct 16 ms 1792 KB Output is correct
7 Runtime error 19 ms 1948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 11624 KB Output is correct
2 Correct 345 ms 13556 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 315 ms 11360 KB Output is correct
5 Correct 329 ms 15832 KB Output is correct
6 Correct 311 ms 15612 KB Output is correct
7 Incorrect 349 ms 14896 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 11696 KB Output is correct
2 Correct 371 ms 13568 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 288 ms 11328 KB Output is correct
5 Correct 346 ms 15616 KB Output is correct
6 Correct 346 ms 15712 KB Output is correct
7 Incorrect 305 ms 14940 KB Wrong Answer [6]
8 Halted 0 ms 0 KB -