oj.uz

답안 #522065

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522065 2022-02-03T17:36:35 Z new_acc 길고양이 (JOI20_stray) C++14
15 / 100
 63 ms 17800 KB 
#include "Anthony.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < int(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e4+10;
int deg[N],kol[N],kt[N];
bool vis[N];
vi graf[N],num[N];
string s="010011";
void bfs(){
	deque<int> deq;
	deq.push_back(0),vis[0]=1;
	while(deq.size()){
		int v=deq.front();
		deq.pop_front();
		for(auto u:graf[v]){
			if(!vis[u]){
				deg[u]=deg[v]+1,vis[u]=1;
				deq.push_back(u);
			}
		}
	}
}
void dfs(int v,int o,int pop=1){
	if(graf[v].size()>2 or graf[v].size()==1){
		rep(i,graf[v].size()){
			if(graf[v][i]==o) continue;
			kol[num[v][i]]=(pop+1)%2;
		}
	}else{
		if(kt[o]==0 and pop==1) kt[v]=0;
		else kt[v]=(kt[o]+1)%(int)(s.size());
		rep(i,graf[v].size()){
			if(graf[v][i]==o) continue;
			kol[num[v][i]]=int(s[kt[v]])-48;
		}
	}
	rep(i,graf[v].size()){
		int u=graf[v][i];
		if(u==o) continue;
		dfs(u,v,kol[num[v][i]]);
	}
}
vi Mark(int n,int m,int a,int b,vi u,vi v){
	rep(i,m) graf[u[i]].push_back(v[i]),graf[v[i]].push_back(u[i]),num[u[i]].push_back(i),num[v[i]].push_back(i);
	if(b==0){
		bfs();
		rep(i,n) kol[i]=(i==0?0:(kol[i-1]+1)%3);
		vi res;
		rep(i,m) res.push_back(kol[min(deg[u[i]],deg[v[i]])]);
		return res;
	}
	vi wyn;
	dfs(0,0);
	rep(i,m) wyn.push_back(kol[i]);
	return wyn;
}
/*int main(){
	vi res;
	vi u,v;
	u.push_back(0),u.push_back(1),u.push_back(2),u.push_back(3),u.push_back(4),u.push_back(5),u.push_back(6);
	v.push_back(1),v.push_back(2),v.push_back(3),v.push_back(4),v.push_back(5),v.push_back(6),v.push_back(7);
	res=Mark(8,7,2,6,u,v);
	rep(i,res.size()) cout<<res[i]<<"\n";
}*/
#include "Catherine.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(size_t a = 0; a < (size_t)(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e4+10;
int il;
bool strona=0;
int ru=0,pocz=-1,pop=0;
bool znal;
string s;
string og="010011";
string d1="01001",d2="10011",d3="00110",d4="01101",d5="11010",d6="10100";
void Init(int a,int b){
	il=a;
}
int Move(vi t){
	if(il>=3){
		bool c[3];
		c[0]=c[1]=c[2]=0;
		rep(i,t.size()) c[i]=(t[i]>0?1:0);
		if(c[0]>0 and c[1]>0) return 0;
		if(c[1]>0 and c[2]>0) return 1;
		if(c[2]>0 and c[0]>0) return 2;
		if(c[0]) return 0;
		if(c[1]) return 1;
		return 2;
	}
	if(pocz==-1){
		pocz=1;
		if(t[0] and t[1]){
			if(t[0]+t[1]>2){
				strona=1;
				if(t[0]==1){pop=0;return 0;}
				pop=1;
				return 1;
			}
			ru++;
			s+='1',s+='0';
			pop=0;
			return 0;
		}else{
			if(t[0]==1 or t[1]==1){
				strona=1;
				if(t[0]) {pop=0;return 0;}
				pop=1;
				return 1;
			}else{
				if(t[0]){
					s+='0';
					pop=0;
					ru++;
					return 0;
				}else{
					s+='1';
					pop=1;
					ru++;
					return 1;
				}
			}
		}
	}else{
		if(strona){
			if(t[0] and t[1]){
				(pop+=1)%=2;
				return pop;
			}else{
				if(t[0]){pop=0;return 0;}
				pop=1;
				return 1;
			}
		}else{
			if(ru==0){
				strona=1;
				pop=(t[0]>0?0:1);
				return pop;
			}
			if((t[0]>1 and !t[1]) or (t[1]>1 and !t[0]) or(!t[0] and !t[1])) znal=1;
			if(znal){
				ru--;
				return -1;
			}
			if(t[0] and t[1]){
				strona=1;
				(pop+=1)%=2;
				return pop;
			}
			if(ru==3){
				if(t[0]) s+='0';
				if(t[1]) s+='1';
				if(s==d1 or s==d2 or s==d3 or s==d4 or s==d5 or s==d6){
					strona=1;
					if(t[0]) pop=0;
					else pop=1;
					return pop;
				}else{
					ru--;
					znal=1;
					return -1;
				}
			}
			if(t[0]) pop=0,s+='0';
			else pop=1,s+='1';
			ru++;
			return pop;
		}
	}
}
/*int main(){
	Init(2,6);
	vi v;
	v.push_back(2),v.push_back(0);
	cout<<Move(v)<<"\n";
	v[0]=0,v[1]=1;
	cout<<Move(v)<<"\n";
	return 0;
}*/

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 16656 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 34 ms 16064 KB Output is correct
4 Correct 63 ms 17800 KB Output is correct
5 Correct 57 ms 17760 KB Output is correct
6 Correct 37 ms 16436 KB Output is correct
7 Correct 48 ms 16432 KB Output is correct
8 Correct 45 ms 17100 KB Output is correct
9 Correct 47 ms 17144 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 16656 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 34 ms 16064 KB Output is correct
4 Correct 63 ms 17800 KB Output is correct
5 Correct 57 ms 17760 KB Output is correct
6 Correct 37 ms 16436 KB Output is correct
7 Correct 48 ms 16432 KB Output is correct
8 Correct 45 ms 17100 KB Output is correct
9 Correct 47 ms 17144 KB Output is correct
10 Correct 36 ms 14556 KB Output is correct
11 Correct 34 ms 14536 KB Output is correct
12 Correct 33 ms 14524 KB Output is correct
13 Correct 34 ms 14524 KB Output is correct
14 Correct 34 ms 14620 KB Output is correct
15 Correct 39 ms 15052 KB Output is correct
16 Correct 44 ms 17244 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 14344 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 29 ms 13892 KB Output is correct
4 Correct 46 ms 15648 KB Output is correct
5 Correct 56 ms 15520 KB Output is correct
6 Correct 39 ms 14208 KB Output is correct
7 Correct 43 ms 14316 KB Output is correct
8 Correct 47 ms 14860 KB Output is correct
9 Correct 45 ms 14928 KB Output is correct
10 Correct 40 ms 14756 KB Output is correct
11 Correct 49 ms 14964 KB Output is correct
12 Correct 39 ms 14620 KB Output is correct
13 Correct 43 ms 14612 KB Output is correct
14 Correct 48 ms 14848 KB Output is correct
15 Correct 40 ms 14976 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 14344 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 29 ms 13892 KB Output is correct
4 Correct 46 ms 15648 KB Output is correct
5 Correct 56 ms 15520 KB Output is correct
6 Correct 39 ms 14208 KB Output is correct
7 Correct 43 ms 14316 KB Output is correct
8 Correct 47 ms 14860 KB Output is correct
9 Correct 45 ms 14928 KB Output is correct
10 Correct 40 ms 14756 KB Output is correct
11 Correct 49 ms 14964 KB Output is correct
12 Correct 39 ms 14620 KB Output is correct
13 Correct 43 ms 14612 KB Output is correct
14 Correct 48 ms 14848 KB Output is correct
15 Correct 40 ms 14976 KB Output is correct
16 Correct 33 ms 12568 KB Output is correct
17 Correct 33 ms 12540 KB Output is correct
18 Correct 35 ms 12532 KB Output is correct
19 Correct 35 ms 12612 KB Output is correct
20 Correct 40 ms 13156 KB Output is correct
21 Correct 38 ms 12804 KB Output is correct
22 Correct 41 ms 15032 KB Output is correct
23 Correct 35 ms 12672 KB Output is correct
24 Correct 38 ms 12696 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1780 KB Output is correct
2 Correct 2 ms 1508 KB Output is correct
3 Correct 3 ms 1772 KB Output is correct
4 Correct 2 ms 1772 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 2 ms 1772 KB Output is correct
7 Incorrect 2 ms 1772 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 12444 KB Output is correct
2 Correct 40 ms 13284 KB Output is correct
3 Correct 2 ms 1516 KB Output is correct
4 Correct 31 ms 12288 KB Output is correct
5 Correct 42 ms 14560 KB Output is correct
6 Incorrect 41 ms 13660 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 12468 KB Output is correct
2 Incorrect 33 ms 13040 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -