oj.uz

Submission #522109

# Submission time Handle Problem Language Result Execution time Memory
522109 2022-02-03T20:49:07 Z new_acc Stray Cat (JOI20_stray) C++14
15 / 100
 56 ms 17796 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,m;
	cin>>n>>m;
	vi v,u;
	rep(i,m){
		int a,b;
		cin>>a>>b;
		v.push_back(a),u.push_back(b);
	}
	vi wyn=Mark(n,m,2,6,v,u);
	for(auto u:wyn) cout<<u<<"\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 41 ms 16584 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 30 ms 16088 KB Output is correct
4 Correct 52 ms 17796 KB Output is correct
5 Correct 56 ms 17756 KB Output is correct
6 Correct 36 ms 16448 KB Output is correct
7 Correct 36 ms 16448 KB Output is correct
8 Correct 54 ms 17064 KB Output is correct
9 Correct 44 ms 17228 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 16584 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 30 ms 16088 KB Output is correct
4 Correct 52 ms 17796 KB Output is correct
5 Correct 56 ms 17756 KB Output is correct
6 Correct 36 ms 16448 KB Output is correct
7 Correct 36 ms 16448 KB Output is correct
8 Correct 54 ms 17064 KB Output is correct
9 Correct 44 ms 17228 KB Output is correct
10 Correct 37 ms 14476 KB Output is correct
11 Correct 39 ms 14300 KB Output is correct
12 Correct 36 ms 14516 KB Output is correct
13 Correct 33 ms 14540 KB Output is correct
14 Correct 36 ms 14752 KB Output is correct
15 Correct 41 ms 15256 KB Output is correct
16 Correct 50 ms 17340 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14256 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 30 ms 13964 KB Output is correct
4 Correct 45 ms 15580 KB Output is correct
5 Correct 54 ms 15620 KB Output is correct
6 Correct 34 ms 14288 KB Output is correct
7 Correct 40 ms 14440 KB Output is correct
8 Correct 49 ms 14904 KB Output is correct
9 Correct 42 ms 14824 KB Output is correct
10 Correct 39 ms 14744 KB Output is correct
11 Correct 40 ms 14632 KB Output is correct
12 Correct 39 ms 14588 KB Output is correct
13 Correct 40 ms 14752 KB Output is correct
14 Correct 56 ms 14976 KB Output is correct
15 Correct 43 ms 15000 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 14256 KB Output is correct
2 Correct 1 ms 1520 KB Output is correct
3 Correct 30 ms 13964 KB Output is correct
4 Correct 45 ms 15580 KB Output is correct
5 Correct 54 ms 15620 KB Output is correct
6 Correct 34 ms 14288 KB Output is correct
7 Correct 40 ms 14440 KB Output is correct
8 Correct 49 ms 14904 KB Output is correct
9 Correct 42 ms 14824 KB Output is correct
10 Correct 39 ms 14744 KB Output is correct
11 Correct 40 ms 14632 KB Output is correct
12 Correct 39 ms 14588 KB Output is correct
13 Correct 40 ms 14752 KB Output is correct
14 Correct 56 ms 14976 KB Output is correct
15 Correct 43 ms 15000 KB Output is correct
16 Correct 31 ms 12644 KB Output is correct
17 Correct 32 ms 12616 KB Output is correct
18 Correct 35 ms 12532 KB Output is correct
19 Correct 41 ms 12548 KB Output is correct
20 Correct 43 ms 13068 KB Output is correct
21 Correct 34 ms 12896 KB Output is correct
22 Correct 40 ms 15104 KB Output is correct
23 Correct 34 ms 12592 KB Output is correct
24 Correct 34 ms 12708 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1768 KB Output is correct
2 Correct 1 ms 1508 KB Output is correct
3 Correct 2 ms 1780 KB Output is correct
4 Correct 2 ms 1772 KB Output is correct
5 Correct 3 ms 1776 KB Output is correct
6 Correct 2 ms 1772 KB Output is correct
7 Correct 2 ms 1772 KB Output is correct
8 Correct 2 ms 1776 KB Output is correct
9 Incorrect 2 ms 1772 KB Wrong Answer [5]
10 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12500 KB Output is correct
2 Correct 46 ms 13980 KB Output is correct
3 Correct 1 ms 1512 KB Output is correct
4 Correct 29 ms 12252 KB Output is correct
5 Correct 52 ms 15768 KB Output is correct
6 Correct 43 ms 15748 KB Output is correct
7 Incorrect 33 ms 14848 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12508 KB Output is correct
2 Correct 40 ms 13928 KB Output is correct
3 Correct 1 ms 1512 KB Output is correct
4 Correct 30 ms 12204 KB Output is correct
5 Correct 49 ms 15964 KB Output is correct
6 Correct 51 ms 15876 KB Output is correct
7 Correct 49 ms 14916 KB Output is correct
8 Incorrect 40 ms 14880 KB Wrong Answer [5]
9 Halted 0 ms 0 KB -