oj.uz

Submission #212941

# Submission time Handle Problem Language Result Execution time Memory
212941 2020-03-24T15:03:56 Z ryansee Stray Cat (JOI20_stray) C++14
85 / 100
 428 ms 17276 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[] = {1,0,0,1,1,0};
}  // 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+5)%6);
		}else{
			for(auto i:v[x])if(i^p){
				depth[i]=depth[x]+1, dfs(i,x,(V[x]==1?5:4));
			}
		}
	};
	dfs(0,0,5);
	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[] = {1,0,0,1,1,0};
}  // namespace

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

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:88:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(auto i:C) cerr<<i<<' '; cerr<<'\n';
     ^~~
Catherine.cpp:88: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 Incorrect 307 ms 16960 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 307 ms 16960 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 14676 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 299 ms 12920 KB Output is correct
4 Correct 332 ms 17276 KB Output is correct
5 Incorrect 311 ms 17148 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 14676 KB Output is correct
2 Correct 9 ms 1536 KB Output is correct
3 Correct 299 ms 12920 KB Output is correct
4 Correct 332 ms 17276 KB Output is correct
5 Incorrect 311 ms 17148 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1792 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 20 ms 1792 KB Output is correct
4 Correct 16 ms 1792 KB Output is correct
5 Correct 17 ms 1792 KB Output is correct
6 Correct 20 ms 1896 KB Output is correct
7 Correct 17 ms 1792 KB Output is correct
8 Correct 16 ms 1792 KB Output is correct
9 Correct 18 ms 1792 KB Output is correct
10 Correct 16 ms 1792 KB Output is correct
11 Correct 16 ms 1792 KB Output is correct
12 Correct 20 ms 1896 KB Output is correct
13 Correct 17 ms 1792 KB Output is correct
14 Correct 17 ms 1792 KB Output is correct
15 Correct 17 ms 1792 KB Output is correct
16 Correct 18 ms 1792 KB Output is correct
17 Correct 18 ms 1792 KB Output is correct
18 Correct 17 ms 1792 KB Output is correct
19 Correct 16 ms 1792 KB Output is correct
20 Correct 16 ms 1792 KB Output is correct
21 Correct 17 ms 1792 KB Output is correct
22 Correct 19 ms 1792 KB Output is correct
23 Correct 20 ms 1792 KB Output is correct
24 Correct 21 ms 1792 KB Output is correct
25 Correct 18 ms 1744 KB Output is correct
26 Correct 17 ms 1792 KB Output is correct
27 Correct 16 ms 1792 KB Output is correct
28 Correct 18 ms 1792 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 11560 KB Output is correct
2 Correct 302 ms 13300 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 313 ms 11480 KB Output is correct
5 Correct 327 ms 15708 KB Output is correct
6 Correct 355 ms 15612 KB Output is correct
7 Correct 316 ms 14712 KB Output is correct
8 Correct 329 ms 14824 KB Output is correct
9 Correct 337 ms 15728 KB Output is correct
10 Correct 317 ms 15536 KB Output is correct
11 Correct 353 ms 15612 KB Output is correct
12 Correct 326 ms 15500 KB Output is correct
13 Correct 330 ms 15712 KB Output is correct
14 Correct 330 ms 15752 KB Output is correct
15 Correct 319 ms 15600 KB Output is correct
16 Correct 345 ms 15600 KB Output is correct
17 Correct 322 ms 15328 KB Output is correct
18 Correct 351 ms 15320 KB Output is correct
19 Correct 316 ms 15328 KB Output is correct
20 Correct 310 ms 15492 KB Output is correct
21 Correct 316 ms 15296 KB Output is correct
22 Correct 328 ms 15284 KB Output is correct
23 Correct 300 ms 11488 KB Output is correct
24 Correct 310 ms 11604 KB Output is correct
25 Correct 322 ms 12184 KB Output is correct
26 Correct 318 ms 12280 KB Output is correct
27 Correct 325 ms 13520 KB Output is correct
28 Correct 326 ms 13536 KB Output is correct
29 Correct 316 ms 13632 KB Output is correct
30 Correct 310 ms 13512 KB Output is correct
31 Correct 312 ms 11600 KB Output is correct
32 Correct 318 ms 11476 KB Output is correct
33 Correct 315 ms 12256 KB Output is correct
34 Correct 312 ms 12276 KB Output is correct
35 Correct 335 ms 13336 KB Output is correct
36 Correct 333 ms 13264 KB Output is correct
37 Correct 324 ms 13320 KB Output is correct
38 Correct 317 ms 13280 KB Output is correct
39 Correct 310 ms 13424 KB Output is correct
40 Correct 333 ms 13280 KB Output is correct
41 Correct 345 ms 14308 KB Output is correct
42 Correct 345 ms 14308 KB Output is correct
43 Correct 325 ms 14312 KB Output is correct
44 Correct 323 ms 14340 KB Output is correct
45 Correct 304 ms 14308 KB Output is correct
46 Correct 301 ms 14292 KB Output is correct
47 Correct 319 ms 13128 KB Output is correct
48 Correct 311 ms 13200 KB Output is correct
49 Correct 305 ms 13008 KB Output is correct
50 Correct 306 ms 13128 KB Output is correct
51 Correct 305 ms 12020 KB Output is correct
52 Correct 410 ms 11860 KB Output is correct
53 Correct 335 ms 11892 KB Output is correct
54 Correct 309 ms 11992 KB Output is correct
55 Correct 329 ms 11908 KB Output is correct
56 Correct 285 ms 11900 KB Output is correct
57 Correct 367 ms 11712 KB Output is correct
58 Correct 428 ms 11728 KB Output is correct
59 Correct 363 ms 11908 KB Output is correct
60 Correct 292 ms 11952 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 11688 KB Output is correct
2 Correct 324 ms 13372 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 292 ms 11460 KB Output is correct
5 Correct 319 ms 15728 KB Output is correct
6 Correct 305 ms 15728 KB Output is correct
7 Correct 319 ms 14796 KB Output is correct
8 Correct 296 ms 14744 KB Output is correct
9 Correct 348 ms 15836 KB Output is correct
10 Correct 349 ms 15692 KB Output is correct
11 Correct 350 ms 15984 KB Output is correct
12 Correct 300 ms 15600 KB Output is correct
13 Correct 340 ms 15556 KB Output is correct
14 Correct 317 ms 15728 KB Output is correct
15 Correct 330 ms 15724 KB Output is correct
16 Correct 330 ms 15584 KB Output is correct
17 Correct 315 ms 15344 KB Output is correct
18 Correct 334 ms 15308 KB Output is correct
19 Correct 323 ms 15360 KB Output is correct
20 Correct 349 ms 15332 KB Output is correct
21 Correct 352 ms 15308 KB Output is correct
22 Correct 369 ms 15280 KB Output is correct
23 Correct 324 ms 11656 KB Output is correct
24 Correct 308 ms 11516 KB Output is correct
25 Correct 321 ms 12520 KB Output is correct
26 Correct 321 ms 12256 KB Output is correct
27 Correct 298 ms 13676 KB Output is correct
28 Correct 297 ms 13596 KB Output is correct
29 Correct 310 ms 13976 KB Output is correct
30 Correct 311 ms 13568 KB Output is correct
31 Correct 279 ms 11588 KB Output is correct
32 Correct 292 ms 11712 KB Output is correct
33 Correct 338 ms 12584 KB Output is correct
34 Correct 291 ms 12272 KB Output is correct
35 Correct 308 ms 13304 KB Output is correct
36 Correct 316 ms 13288 KB Output is correct
37 Correct 307 ms 13288 KB Output is correct
38 Correct 318 ms 13408 KB Output is correct
39 Correct 324 ms 13508 KB Output is correct
40 Correct 312 ms 13280 KB Output is correct
41 Correct 335 ms 14400 KB Output is correct
42 Correct 317 ms 14264 KB Output is correct
43 Correct 316 ms 14380 KB Output is correct
44 Correct 316 ms 14328 KB Output is correct
45 Correct 317 ms 14196 KB Output is correct
46 Correct 311 ms 14296 KB Output is correct
47 Correct 302 ms 13184 KB Output is correct
48 Correct 308 ms 13148 KB Output is correct
49 Correct 302 ms 13048 KB Output is correct
50 Correct 313 ms 13112 KB Output is correct
51 Correct 293 ms 11896 KB Output is correct
52 Correct 331 ms 11868 KB Output is correct
53 Correct 306 ms 11864 KB Output is correct
54 Correct 307 ms 11804 KB Output is correct
55 Correct 300 ms 11872 KB Output is correct
56 Correct 311 ms 11872 KB Output is correct
57 Correct 301 ms 11704 KB Output is correct
58 Correct 312 ms 11624 KB Output is correct
59 Correct 301 ms 11940 KB Output is correct
60 Correct 309 ms 11916 KB Output is correct