oj.uz

Submission #522105

# Submission time Handle Problem Language Result Execution time Memory
522105 2022-02-03T20:35:35 Z new_acc Stray Cat (JOI20_stray) C++14
15 / 100
 49 ms 18296 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 NN=2e4+10;
int deg[NN],kol[NN],kt[NN];
bool vis[NN];
vi graf[NN],num[NN];
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){
	string s="010011";
	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(){
	int n=4,m=5;
	vi u,v;
	v.push_back(1),v.push_back(2),v.push_back(3),v.push_back(4);
	u.push_back(0),u.push_back(1),u.push_back(2),u.push_back(3);
	vector<int> mm=Mark(n,m,2,6,v,u);
	for(int i=1;i<=m;i++) cout<<mm[i-1]<<"\n";
}*/
#include "Catherine.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 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";
vi akt;
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;
			}
			akt.push_back(0);
			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';
					s+='0';
					pop=0;
					akt.push_back(0);
					return 0;
				}else{
					s+='1';
					s+='1';
					pop=1;
					akt.push_back(1);
					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((int)akt.size()==0){
				strona=1;
				pop=(t[0]>0?0:1);
				return pop;
			}
			if(znal){
				int lo=akt.back();
				akt.pop_back();
				return lo;
			}
			if((t[0]>1 and !t[1]) or (t[1]>1 and !t[0]) or (!t[0] and !t[1])) znal=1;
			if(znal){akt.pop_back();return -1;}
			if(t[0] and t[1]){
				strona=1;
				(pop+=1)%=2;
				return pop;
			}
			if((int)akt.size()==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){
					znal=1;
					return -1;
				}else{
					strona=1;
					if(t[0]) pop=0;
					else pop=1;
					return pop;
				}
			}
			if(t[0]) pop=0,s+='0';
			else pop=1,s+='1';
			akt.push_back(pop);
			return pop;
		}
	}
}
/*int main(){
	vector<int> v;
	v.push_back(1),v.push_back(1);
	cout<<Move(v)<<"\n";
	v[1]=0;
	cout<<Move(v)<<"\n";
	v[0]=0;
	cout<<Move(v)<<"\n";
	v[0]=1;
	cout<<Move(v)<<"\n";
	v[0]=0,v[1]=1;
	cout<<Move(v)<<"\n";
	v[0]=1,v[1]=0;
	cout<<Move(v)<<"\n";	
}*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17032 KB Output is correct
2 Correct 1 ms 1524 KB Output is correct
3 Correct 33 ms 16408 KB Output is correct
4 Correct 47 ms 18296 KB Output is correct
5 Correct 47 ms 18088 KB Output is correct
6 Correct 39 ms 16992 KB Output is correct
7 Correct 38 ms 16928 KB Output is correct
8 Correct 45 ms 17520 KB Output is correct
9 Correct 43 ms 17516 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 17032 KB Output is correct
2 Correct 1 ms 1524 KB Output is correct
3 Correct 33 ms 16408 KB Output is correct
4 Correct 47 ms 18296 KB Output is correct
5 Correct 47 ms 18088 KB Output is correct
6 Correct 39 ms 16992 KB Output is correct
7 Correct 38 ms 16928 KB Output is correct
8 Correct 45 ms 17520 KB Output is correct
9 Correct 43 ms 17516 KB Output is correct
10 Correct 34 ms 14776 KB Output is correct
11 Correct 34 ms 14812 KB Output is correct
12 Correct 46 ms 14800 KB Output is correct
13 Correct 34 ms 14852 KB Output is correct
14 Correct 34 ms 15032 KB Output is correct
15 Correct 41 ms 15404 KB Output is correct
16 Correct 42 ms 17624 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14644 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 31 ms 14232 KB Output is correct
4 Correct 45 ms 15960 KB Output is correct
5 Correct 49 ms 16092 KB Output is correct
6 Correct 40 ms 14696 KB Output is correct
7 Correct 37 ms 14804 KB Output is correct
8 Correct 44 ms 15360 KB Output is correct
9 Correct 41 ms 15368 KB Output is correct
10 Correct 38 ms 15020 KB Output is correct
11 Correct 42 ms 15016 KB Output is correct
12 Correct 40 ms 15044 KB Output is correct
13 Correct 39 ms 14992 KB Output is correct
14 Correct 41 ms 15356 KB Output is correct
15 Correct 42 ms 15300 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14644 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 31 ms 14232 KB Output is correct
4 Correct 45 ms 15960 KB Output is correct
5 Correct 49 ms 16092 KB Output is correct
6 Correct 40 ms 14696 KB Output is correct
7 Correct 37 ms 14804 KB Output is correct
8 Correct 44 ms 15360 KB Output is correct
9 Correct 41 ms 15368 KB Output is correct
10 Correct 38 ms 15020 KB Output is correct
11 Correct 42 ms 15016 KB Output is correct
12 Correct 40 ms 15044 KB Output is correct
13 Correct 39 ms 14992 KB Output is correct
14 Correct 41 ms 15356 KB Output is correct
15 Correct 42 ms 15300 KB Output is correct
16 Correct 31 ms 13140 KB Output is correct
17 Correct 34 ms 12980 KB Output is correct
18 Correct 34 ms 13048 KB Output is correct
19 Correct 35 ms 12884 KB Output is correct
20 Correct 38 ms 13560 KB Output is correct
21 Correct 35 ms 13364 KB Output is correct
22 Correct 38 ms 15504 KB Output is correct
23 Correct 33 ms 13056 KB Output is correct
24 Correct 33 ms 13092 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1776 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 2 ms 1784 KB Output is correct
4 Correct 2 ms 1904 KB Output is correct
5 Correct 2 ms 1824 KB Output is correct
6 Correct 2 ms 1904 KB Output is correct
7 Correct 2 ms 1904 KB Output is correct
8 Correct 3 ms 1788 KB Output is correct
9 Incorrect 2 ms 1904 KB Wrong Answer [5]
10 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 12984 KB Output is correct
2 Correct 37 ms 14308 KB Output is correct
3 Correct 1 ms 1516 KB Output is correct
4 Correct 28 ms 12668 KB Output is correct
5 Correct 48 ms 16104 KB Output is correct
6 Correct 45 ms 16164 KB Output is correct
7 Incorrect 36 ms 15244 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 12948 KB Output is correct
2 Correct 39 ms 14296 KB Output is correct
3 Correct 1 ms 1516 KB Output is correct
4 Correct 28 ms 12632 KB Output is correct
5 Correct 44 ms 16112 KB Output is correct
6 Correct 46 ms 16220 KB Output is correct
7 Correct 39 ms 15228 KB Output is correct
8 Incorrect 32 ms 15216 KB Wrong Answer [5]
9 Halted 0 ms 0 KB -