oj.uz

Submission #522064

# Submission time Handle Problem Language Result Execution time Memory
522064 2022-02-03T17:34:38 Z new_acc Stray Cat (JOI20_stray) C++14
15 / 100
 61 ms 18124 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;
			else pop=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

# Verdict Execution time Memory Grader output
1 Correct 38 ms 17048 KB Output is correct
2 Correct 1 ms 1496 KB Output is correct
3 Correct 34 ms 16432 KB Output is correct
4 Correct 61 ms 18124 KB Output is correct
5 Correct 50 ms 18072 KB Output is correct
6 Correct 47 ms 16856 KB Output is correct
7 Correct 38 ms 16832 KB Output is correct
8 Correct 43 ms 17528 KB Output is correct
9 Correct 42 ms 17536 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 17048 KB Output is correct
2 Correct 1 ms 1496 KB Output is correct
3 Correct 34 ms 16432 KB Output is correct
4 Correct 61 ms 18124 KB Output is correct
5 Correct 50 ms 18072 KB Output is correct
6 Correct 47 ms 16856 KB Output is correct
7 Correct 38 ms 16832 KB Output is correct
8 Correct 43 ms 17528 KB Output is correct
9 Correct 42 ms 17536 KB Output is correct
10 Correct 36 ms 14744 KB Output is correct
11 Correct 34 ms 14844 KB Output is correct
12 Correct 47 ms 14816 KB Output is correct
13 Correct 48 ms 14728 KB Output is correct
14 Correct 37 ms 15084 KB Output is correct
15 Correct 38 ms 15484 KB Output is correct
16 Correct 46 ms 17672 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 14564 KB Output is correct
2 Correct 2 ms 1444 KB Output is correct
3 Correct 32 ms 14284 KB Output is correct
4 Correct 44 ms 15992 KB Output is correct
5 Correct 45 ms 16064 KB Output is correct
6 Correct 36 ms 14728 KB Output is correct
7 Correct 38 ms 14696 KB Output is correct
8 Correct 44 ms 15304 KB Output is correct
9 Correct 41 ms 15540 KB Output is correct
10 Correct 39 ms 15016 KB Output is correct
11 Correct 40 ms 15036 KB Output is correct
12 Correct 40 ms 15104 KB Output is correct
13 Correct 41 ms 15112 KB Output is correct
14 Correct 52 ms 15400 KB Output is correct
15 Correct 48 ms 15328 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 14564 KB Output is correct
2 Correct 2 ms 1444 KB Output is correct
3 Correct 32 ms 14284 KB Output is correct
4 Correct 44 ms 15992 KB Output is correct
5 Correct 45 ms 16064 KB Output is correct
6 Correct 36 ms 14728 KB Output is correct
7 Correct 38 ms 14696 KB Output is correct
8 Correct 44 ms 15304 KB Output is correct
9 Correct 41 ms 15540 KB Output is correct
10 Correct 39 ms 15016 KB Output is correct
11 Correct 40 ms 15036 KB Output is correct
12 Correct 40 ms 15104 KB Output is correct
13 Correct 41 ms 15112 KB Output is correct
14 Correct 52 ms 15400 KB Output is correct
15 Correct 48 ms 15328 KB Output is correct
16 Correct 30 ms 13084 KB Output is correct
17 Correct 31 ms 13084 KB Output is correct
18 Correct 33 ms 12944 KB Output is correct
19 Correct 33 ms 12988 KB Output is correct
20 Correct 43 ms 13548 KB Output is correct
21 Correct 39 ms 13268 KB Output is correct
22 Correct 44 ms 15588 KB Output is correct
23 Correct 37 ms 13072 KB Output is correct
24 Correct 34 ms 12956 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 2 ms 1588 KB Output is correct
3 Correct 2 ms 1720 KB Output is correct
4 Correct 2 ms 1792 KB Output is correct
5 Correct 2 ms 1776 KB Output is correct
6 Correct 2 ms 1848 KB Output is correct
7 Incorrect 2 ms 1768 KB Wrong Answer [5]
8 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12952 KB Output is correct
2 Correct 41 ms 13780 KB Output is correct
3 Correct 2 ms 1464 KB Output is correct
4 Correct 35 ms 12600 KB Output is correct
5 Correct 48 ms 14884 KB Output is correct
6 Incorrect 39 ms 14032 KB Wrong Answer [5]
7 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

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