oj.uz

답안 #212954

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
212954 2020-03-24T15:31:01 Z ryansee 길고양이 (JOI20_stray) C++14
85 / 100
 391 ms 17224 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+1)%6);
		}else{
			for(auto i:v[x])if(i^p){
				depth[i]=depth[x]+1, dfs(i,x,(V[x]==1?1:0));
			}
		}
	};
	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[] = {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;
		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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 319 ms 16976 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 319 ms 16976 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 14692 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 300 ms 12904 KB Output is correct
4 Correct 309 ms 17224 KB Output is correct
5 Correct 318 ms 17216 KB Output is correct
6 Incorrect 311 ms 13808 KB Wrong Answer [6]
7 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 14692 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 300 ms 12904 KB Output is correct
4 Correct 309 ms 17224 KB Output is correct
5 Correct 318 ms 17216 KB Output is correct
6 Incorrect 311 ms 13808 KB Wrong Answer [6]
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 1792 KB Output is correct
2 Correct 10 ms 1536 KB Output is correct
3 Correct 16 ms 1792 KB Output is correct
4 Correct 18 ms 1792 KB Output is correct
5 Correct 16 ms 1792 KB Output is correct
6 Correct 20 ms 1792 KB Output is correct
7 Correct 17 ms 1792 KB Output is correct
8 Correct 16 ms 1792 KB Output is correct
9 Correct 46 ms 1792 KB Output is correct
10 Correct 16 ms 1792 KB Output is correct
11 Correct 19 ms 1792 KB Output is correct
12 Correct 17 ms 1792 KB Output is correct
13 Correct 17 ms 1792 KB Output is correct
14 Correct 18 ms 1792 KB Output is correct
15 Correct 18 ms 1888 KB Output is correct
16 Correct 16 ms 1792 KB Output is correct
17 Correct 18 ms 1792 KB Output is correct
18 Correct 17 ms 1880 KB Output is correct
19 Correct 15 ms 1792 KB Output is correct
20 Correct 16 ms 1792 KB Output is correct
21 Correct 16 ms 1792 KB Output is correct
22 Correct 20 ms 1792 KB Output is correct
23 Correct 18 ms 1792 KB Output is correct
24 Correct 17 ms 1792 KB Output is correct
25 Correct 18 ms 1792 KB Output is correct
26 Correct 17 ms 1792 KB Output is correct
27 Correct 18 ms 1744 KB Output is correct
28 Correct 18 ms 1680 KB Output is correct

Subtask #6
71.0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 313 ms 11616 KB Output is correct
2 Correct 327 ms 13440 KB Output is correct
3 Correct 10 ms 1536 KB Output is correct
4 Correct 317 ms 11244 KB Output is correct
5 Correct 322 ms 15780 KB Output is correct
6 Correct 339 ms 15572 KB Output is correct
7 Correct 348 ms 14704 KB Output is correct
8 Correct 319 ms 14772 KB Output is correct
9 Correct 345 ms 15772 KB Output is correct
10 Correct 336 ms 15740 KB Output is correct
11 Correct 331 ms 15680 KB Output is correct
12 Correct 310 ms 15728 KB Output is correct
13 Correct 336 ms 15836 KB Output is correct
14 Correct 322 ms 15588 KB Output is correct
15 Correct 391 ms 15584 KB Output is correct
16 Correct 326 ms 15820 KB Output is correct
17 Correct 306 ms 15404 KB Output is correct
18 Correct 317 ms 15460 KB Output is correct
19 Correct 320 ms 15460 KB Output is correct
20 Correct 302 ms 15460 KB Output is correct
21 Correct 316 ms 15328 KB Output is correct
22 Correct 310 ms 15344 KB Output is correct
23 Correct 298 ms 11580 KB Output is correct
24 Correct 291 ms 11548 KB Output is correct
25 Correct 318 ms 12488 KB Output is correct
26 Correct 289 ms 12280 KB Output is correct
27 Correct 326 ms 13824 KB Output is correct
28 Correct 326 ms 13424 KB Output is correct
29 Correct 358 ms 13536 KB Output is correct
30 Correct 307 ms 13512 KB Output is correct
31 Correct 343 ms 11720 KB Output is correct
32 Correct 320 ms 11656 KB Output is correct
33 Correct 341 ms 12232 KB Output is correct
34 Correct 303 ms 12164 KB Output is correct
35 Correct 311 ms 13336 KB Output is correct
36 Correct 320 ms 13300 KB Output is correct
37 Correct 312 ms 13312 KB Output is correct
38 Correct 306 ms 13288 KB Output is correct
39 Correct 302 ms 13320 KB Output is correct
40 Correct 307 ms 13384 KB Output is correct
41 Correct 327 ms 14304 KB Output is correct
42 Correct 319 ms 14304 KB Output is correct
43 Correct 314 ms 14384 KB Output is correct
44 Correct 311 ms 14320 KB Output is correct
45 Correct 322 ms 14236 KB Output is correct
46 Correct 323 ms 14244 KB Output is correct
47 Correct 340 ms 13068 KB Output is correct
48 Correct 312 ms 13040 KB Output is correct
49 Correct 343 ms 13136 KB Output is correct
50 Correct 337 ms 13340 KB Output is correct
51 Correct 321 ms 11872 KB Output is correct
52 Correct 331 ms 11888 KB Output is correct
53 Correct 322 ms 11840 KB Output is correct
54 Correct 314 ms 11880 KB Output is correct
55 Correct 304 ms 11876 KB Output is correct
56 Correct 316 ms 11836 KB Output is correct
57 Correct 323 ms 11588 KB Output is correct
58 Correct 324 ms 11600 KB Output is correct
59 Correct 328 ms 11844 KB Output is correct
60 Correct 336 ms 11964 KB Output is correct

Subtask #7
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 301 ms 11556 KB Output is correct
2 Correct 314 ms 13280 KB Output is correct
3 Correct 11 ms 1536 KB Output is correct
4 Correct 311 ms 11448 KB Output is correct
5 Correct 334 ms 15584 KB Output is correct
6 Correct 329 ms 15720 KB Output is correct
7 Correct 323 ms 14884 KB Output is correct
8 Correct 315 ms 14824 KB Output is correct
9 Correct 314 ms 15648 KB Output is correct
10 Correct 328 ms 15688 KB Output is correct
11 Correct 316 ms 15524 KB Output is correct
12 Correct 316 ms 15600 KB Output is correct
13 Correct 339 ms 15672 KB Output is correct
14 Correct 323 ms 15736 KB Output is correct
15 Correct 337 ms 15528 KB Output is correct
16 Correct 321 ms 15712 KB Output is correct
17 Correct 340 ms 15272 KB Output is correct
18 Correct 328 ms 15268 KB Output is correct
19 Correct 333 ms 15228 KB Output is correct
20 Correct 351 ms 15328 KB Output is correct
21 Correct 352 ms 15504 KB Output is correct
22 Correct 325 ms 15296 KB Output is correct
23 Correct 326 ms 11524 KB Output is correct
24 Correct 309 ms 11872 KB Output is correct
25 Correct 321 ms 12248 KB Output is correct
26 Correct 294 ms 12264 KB Output is correct
27 Correct 326 ms 13580 KB Output is correct
28 Correct 331 ms 13580 KB Output is correct
29 Correct 334 ms 13724 KB Output is correct
30 Correct 324 ms 13496 KB Output is correct
31 Correct 320 ms 11656 KB Output is correct
32 Correct 311 ms 11536 KB Output is correct
33 Correct 305 ms 12364 KB Output is correct
34 Correct 319 ms 12256 KB Output is correct
35 Correct 324 ms 13316 KB Output is correct
36 Correct 308 ms 13344 KB Output is correct
37 Correct 338 ms 13412 KB Output is correct
38 Correct 337 ms 13296 KB Output is correct
39 Correct 321 ms 13204 KB Output is correct
40 Correct 339 ms 13328 KB Output is correct
41 Correct 351 ms 14316 KB Output is correct
42 Correct 328 ms 14468 KB Output is correct
43 Correct 314 ms 14352 KB Output is correct
44 Correct 323 ms 14412 KB Output is correct
45 Correct 320 ms 14320 KB Output is correct
46 Correct 320 ms 14404 KB Output is correct
47 Correct 348 ms 13096 KB Output is correct
48 Correct 325 ms 13180 KB Output is correct
49 Correct 319 ms 12992 KB Output is correct
50 Correct 313 ms 13172 KB Output is correct
51 Correct 315 ms 11880 KB Output is correct
52 Correct 314 ms 11812 KB Output is correct
53 Correct 301 ms 11896 KB Output is correct
54 Correct 318 ms 11712 KB Output is correct
55 Correct 301 ms 11896 KB Output is correct
56 Correct 312 ms 11896 KB Output is correct
57 Correct 329 ms 11560 KB Output is correct
58 Correct 305 ms 11720 KB Output is correct
59 Correct 305 ms 11744 KB Output is correct
60 Correct 320 ms 11884 KB Output is correct