oj.uz

Submission #522047

# Submission time Handle Problem Language Result Execution time Memory
522047 2022-02-03T16:18:11 Z new_acc Stray Cat (JOI20_stray) C++14
15 / 100
 55 ms 18168 KB 
#include "Anthony.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 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);
	v.push_back(1),v.push_back(2),v.push_back(3),v.push_back(4),v.push_back(5),v.push_back(6);
	res=Mark(7,6,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;
					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;
				}
			}
		}
	}
	return 0;
}
/*int main(){
	Init(2,6);
	vi v;
	v.push_back(0),v.push_back(2);
	cout<<Move(v)<<"\n";
	v[1]=0;
	cout<<Move(v)<<"\n";
}*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17068 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 33 ms 16520 KB Output is correct
4 Correct 49 ms 18152 KB Output is correct
5 Correct 53 ms 18168 KB Output is correct
6 Correct 50 ms 16932 KB Output is correct
7 Correct 38 ms 16872 KB Output is correct
8 Correct 44 ms 17564 KB Output is correct
9 Correct 42 ms 17532 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 17068 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 33 ms 16520 KB Output is correct
4 Correct 49 ms 18152 KB Output is correct
5 Correct 53 ms 18168 KB Output is correct
6 Correct 50 ms 16932 KB Output is correct
7 Correct 38 ms 16872 KB Output is correct
8 Correct 44 ms 17564 KB Output is correct
9 Correct 42 ms 17532 KB Output is correct
10 Correct 34 ms 14720 KB Output is correct
11 Correct 40 ms 14860 KB Output is correct
12 Correct 41 ms 14804 KB Output is correct
13 Correct 36 ms 14772 KB Output is correct
14 Correct 38 ms 15200 KB Output is correct
15 Correct 38 ms 15536 KB Output is correct
16 Correct 43 ms 17616 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14572 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 36 ms 14220 KB Output is correct
4 Correct 46 ms 15968 KB Output is correct
5 Correct 48 ms 15936 KB Output is correct
6 Correct 36 ms 14724 KB Output is correct
7 Correct 37 ms 14676 KB Output is correct
8 Correct 54 ms 15192 KB Output is correct
9 Correct 40 ms 15240 KB Output is correct
10 Correct 40 ms 14976 KB Output is correct
11 Correct 40 ms 15092 KB Output is correct
12 Correct 40 ms 14980 KB Output is correct
13 Correct 46 ms 14964 KB Output is correct
14 Correct 44 ms 15348 KB Output is correct
15 Correct 41 ms 15384 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14572 KB Output is correct
2 Correct 1 ms 1516 KB Output is correct
3 Correct 36 ms 14220 KB Output is correct
4 Correct 46 ms 15968 KB Output is correct
5 Correct 48 ms 15936 KB Output is correct
6 Correct 36 ms 14724 KB Output is correct
7 Correct 37 ms 14676 KB Output is correct
8 Correct 54 ms 15192 KB Output is correct
9 Correct 40 ms 15240 KB Output is correct
10 Correct 40 ms 14976 KB Output is correct
11 Correct 40 ms 15092 KB Output is correct
12 Correct 40 ms 14980 KB Output is correct
13 Correct 46 ms 14964 KB Output is correct
14 Correct 44 ms 15348 KB Output is correct
15 Correct 41 ms 15384 KB Output is correct
16 Correct 31 ms 13052 KB Output is correct
17 Correct 33 ms 13076 KB Output is correct
18 Correct 34 ms 12928 KB Output is correct
19 Correct 40 ms 12908 KB Output is correct
20 Correct 55 ms 13496 KB Output is correct
21 Correct 37 ms 13356 KB Output is correct
22 Correct 39 ms 15492 KB Output is correct
23 Correct 35 ms 13044 KB Output is correct
24 Correct 40 ms 13164 KB Output is correct

Subtask #5
0 / 5.0

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

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 12900 KB Output is correct
2 Incorrect 40 ms 13520 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 12804 KB Output is correct
2 Incorrect 32 ms 13484 KB Wrong Answer [5]
3 Halted 0 ms 0 KB -