oj.uz

Submission #212957

# Submission time Handle Problem Language Result Execution time Memory
212957 2020-03-24T15:34:19 Z ryansee Stray Cat (JOI20_stray) C++14
85 / 100
 383 ms 17328 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?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;
}

#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) {
	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 297 ms 17152 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

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

Subtask #3
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 14708 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 383 ms 12976 KB Output is correct
4 Correct 316 ms 17288 KB Output is correct
5 Incorrect 352 ms 17328 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 14708 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 383 ms 12976 KB Output is correct
4 Correct 316 ms 17288 KB Output is correct
5 Incorrect 352 ms 17328 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 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 20 ms 1792 KB Output is correct
5 Correct 17 ms 1792 KB Output is correct
6 Correct 17 ms 1792 KB Output is correct
7 Correct 20 ms 1792 KB Output is correct
8 Correct 17 ms 1792 KB Output is correct
9 Correct 17 ms 1792 KB Output is correct
10 Correct 17 ms 1792 KB Output is correct
11 Correct 17 ms 1960 KB Output is correct
12 Correct 20 ms 1792 KB Output is correct
13 Correct 20 ms 1896 KB Output is correct
14 Correct 20 ms 1792 KB Output is correct
15 Correct 13 ms 1744 KB Output is correct
16 Correct 16 ms 1792 KB Output is correct
17 Correct 19 ms 1792 KB Output is correct
18 Correct 16 ms 1792 KB Output is correct
19 Correct 17 ms 1792 KB Output is correct
20 Correct 20 ms 1792 KB Output is correct
21 Correct 19 ms 1792 KB Output is correct
22 Correct 20 ms 1792 KB Output is correct
23 Correct 17 ms 1792 KB Output is correct
24 Correct 16 ms 1792 KB Output is correct
25 Correct 17 ms 1792 KB Output is correct
26 Correct 18 ms 1856 KB Output is correct
27 Correct 17 ms 1792 KB Output is correct
28 Correct 17 ms 1792 KB Output is correct

Subtask #6
71.0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 11492 KB Output is correct
2 Correct 334 ms 13476 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 301 ms 11428 KB Output is correct
5 Correct 326 ms 15656 KB Output is correct
6 Correct 337 ms 15540 KB Output is correct
7 Correct 318 ms 14836 KB Output is correct
8 Correct 337 ms 14800 KB Output is correct
9 Correct 336 ms 15708 KB Output is correct
10 Correct 327 ms 15700 KB Output is correct
11 Correct 330 ms 15652 KB Output is correct
12 Correct 319 ms 15728 KB Output is correct
13 Correct 334 ms 15576 KB Output is correct
14 Correct 366 ms 15760 KB Output is correct
15 Correct 335 ms 15720 KB Output is correct
16 Correct 352 ms 15712 KB Output is correct
17 Correct 317 ms 15344 KB Output is correct
18 Correct 315 ms 15352 KB Output is correct
19 Correct 332 ms 15400 KB Output is correct
20 Correct 338 ms 15332 KB Output is correct
21 Correct 336 ms 15344 KB Output is correct
22 Correct 328 ms 15380 KB Output is correct
23 Correct 319 ms 11576 KB Output is correct
24 Correct 298 ms 11680 KB Output is correct
25 Correct 325 ms 12376 KB Output is correct
26 Correct 312 ms 12152 KB Output is correct
27 Correct 321 ms 13560 KB Output is correct
28 Correct 334 ms 13492 KB Output is correct
29 Correct 318 ms 13536 KB Output is correct
30 Correct 331 ms 13744 KB Output is correct
31 Correct 295 ms 11640 KB Output is correct
32 Correct 325 ms 11668 KB Output is correct
33 Correct 334 ms 12204 KB Output is correct
34 Correct 344 ms 12344 KB Output is correct
35 Correct 337 ms 13416 KB Output is correct
36 Correct 328 ms 13420 KB Output is correct
37 Correct 316 ms 13372 KB Output is correct
38 Correct 323 ms 13560 KB Output is correct
39 Correct 316 ms 13524 KB Output is correct
40 Correct 331 ms 13448 KB Output is correct
41 Correct 317 ms 14328 KB Output is correct
42 Correct 314 ms 14320 KB Output is correct
43 Correct 333 ms 14272 KB Output is correct
44 Correct 326 ms 14372 KB Output is correct
45 Correct 324 ms 14340 KB Output is correct
46 Correct 318 ms 14472 KB Output is correct
47 Correct 322 ms 13244 KB Output is correct
48 Correct 328 ms 13132 KB Output is correct
49 Correct 326 ms 13036 KB Output is correct
50 Correct 306 ms 13164 KB Output is correct
51 Correct 313 ms 11752 KB Output is correct
52 Correct 306 ms 11876 KB Output is correct
53 Correct 365 ms 11816 KB Output is correct
54 Correct 299 ms 11872 KB Output is correct
55 Correct 323 ms 11812 KB Output is correct
56 Correct 335 ms 11876 KB Output is correct
57 Correct 334 ms 11968 KB Output is correct
58 Correct 311 ms 11768 KB Output is correct
59 Correct 317 ms 11816 KB Output is correct
60 Correct 310 ms 11888 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 11612 KB Output is correct
2 Correct 316 ms 13328 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 294 ms 11344 KB Output is correct
5 Correct 332 ms 15600 KB Output is correct
6 Correct 339 ms 15616 KB Output is correct
7 Correct 321 ms 14656 KB Output is correct
8 Correct 325 ms 15024 KB Output is correct
9 Correct 333 ms 15600 KB Output is correct
10 Correct 334 ms 15600 KB Output is correct
11 Correct 317 ms 15684 KB Output is correct
12 Correct 320 ms 15804 KB Output is correct
13 Correct 321 ms 15728 KB Output is correct
14 Correct 326 ms 15584 KB Output is correct
15 Correct 319 ms 15800 KB Output is correct
16 Correct 329 ms 15600 KB Output is correct
17 Correct 306 ms 15320 KB Output is correct
18 Correct 371 ms 15368 KB Output is correct
19 Correct 325 ms 15344 KB Output is correct
20 Correct 360 ms 15292 KB Output is correct
21 Correct 315 ms 15328 KB Output is correct
22 Correct 313 ms 15508 KB Output is correct
23 Correct 314 ms 11556 KB Output is correct
24 Correct 326 ms 11548 KB Output is correct
25 Correct 326 ms 12412 KB Output is correct
26 Correct 302 ms 12124 KB Output is correct
27 Correct 316 ms 13496 KB Output is correct
28 Correct 309 ms 13560 KB Output is correct
29 Correct 334 ms 13544 KB Output is correct
30 Correct 308 ms 13512 KB Output is correct
31 Correct 307 ms 11724 KB Output is correct
32 Correct 306 ms 11676 KB Output is correct
33 Correct 333 ms 12300 KB Output is correct
34 Correct 322 ms 12340 KB Output is correct
35 Correct 323 ms 13548 KB Output is correct
36 Correct 289 ms 13424 KB Output is correct
37 Correct 324 ms 13420 KB Output is correct
38 Correct 323 ms 13348 KB Output is correct
39 Correct 328 ms 13476 KB Output is correct
40 Correct 297 ms 13420 KB Output is correct
41 Correct 331 ms 14444 KB Output is correct
42 Correct 316 ms 14328 KB Output is correct
43 Correct 320 ms 14336 KB Output is correct
44 Correct 304 ms 14288 KB Output is correct
45 Correct 298 ms 14376 KB Output is correct
46 Correct 317 ms 14344 KB Output is correct
47 Correct 311 ms 13316 KB Output is correct
48 Correct 299 ms 13168 KB Output is correct
49 Correct 298 ms 12996 KB Output is correct
50 Correct 316 ms 13168 KB Output is correct
51 Correct 325 ms 11892 KB Output is correct
52 Correct 306 ms 11800 KB Output is correct
53 Correct 309 ms 11708 KB Output is correct
54 Correct 309 ms 11808 KB Output is correct
55 Correct 310 ms 11916 KB Output is correct
56 Correct 314 ms 11884 KB Output is correct
57 Correct 321 ms 11756 KB Output is correct
58 Correct 306 ms 11828 KB Output is correct
59 Correct 323 ms 11996 KB Output is correct
60 Correct 311 ms 11936 KB Output is correct