Submission #227529

#	Time	Username	Problem	Language	Result	Execution time	Memory
227529		kshitij_sodani	Trobojnica (COCI19_trobojnica)	C++17	0 / 110	11 ms	12160 KiB

trobojnica

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl "\n"
int it[200001];
int dp[1001][1001][3];
//0 add to first 
//1 add to second
int n;
int find(int aa,int bb,int cc){
	if(dp[aa][bb][cc]>-1){
		return dp[aa][bb][cc];
	}
	/*if(bb==(aa+1)%n){
		dp[aa][bb][cc]=1;
		return 1;
	}
	if(aa==bb){
		dp[aa][bb][cc]=1;
		return 1;
	}*/
//	cout<<aa<<" "<<bb<<" "<<cc<<endl;
	if(bb==(aa+2)%n){
		if(it[aa]==it[(aa+1)%n] or it[(aa+1)%n]==cc or it[aa]==cc){
			dp[aa][bb][cc]=0;
			return 0;
		}
	//	cout<<aa<<","<<bb<<","<<cc<<endl;
		dp[aa][bb][cc]=1;
		return 1;
	}
	dp[aa][bb][cc]=0;
		int ee=(bb-1);
		if(ee<0){
			ee+=n;
		}
		for(int i=0;i<3;i++){
			if(i==it[ee] or i==cc or it[ee]==cc){
				continue;
			}
			dp[aa][bb][cc]=max(find(aa,ee,i),dp[aa][bb][cc]);
		}
		int ff=(aa+1);
		if(ff>=n){
			ff-=n;
		}
		for(int i=0;i<3;i++){
			if(i==it[aa] or i==cc or it[aa]==cc){
				continue;
			}

			dp[aa][bb][cc]=max(find(ff,bb,i),dp[aa][bb][cc]);
		}
	return dp[aa][bb][cc];
}
int find2(int aa,int bb,int cc){
	if(aa!=(bb+1)%n){
		cout<<aa+1<<" "<<bb+1<<" "<<cc+1<<endl;
	}
	if(bb==(aa+2)%n){
		return 1;
	}
	int ee=(bb-1);
	if(ee<0){
		ee+=n;
	}
	int st=0;
	for(int i=0;i<3;i++){
		if(i==it[ee] or i==cc or it[ee]==cc){
			continue;
		}
		if(dp[aa][ee][i]==1 and st==0){
			st=1;
			find2(aa,ee,i);
		}
	}
	int ff=(aa+1);
	if(ff>=n){
		ff-=n;
	}
	for(int i=0;i<3;i++){
		if(i==it[aa] or i==cc or it[aa]==cc){
			continue;
		}
		if(dp[ff][bb][i]==1 and st==0){
			st=1;
			find2(ff,bb,i);
		}
	}
	return 1;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	memset(dp,-1,sizeof(dp));
	char s;
	for(int i=0;i<n;i++){
		cin>>s;
		if(s=='1'){
			it[i]=0;
		}
		else if(s=='2'){
			it[i]=1;
		}
		else{
			it[i]=2;
		}
	}

	int ans=0;
	for(int i=0;i<n;i++){
		int xx=find(i,(i-1+n)%n,it[(i-1+n)%n]);
		if(xx==1){
			cout<<"DA"<<endl;
			find2(i,(i-1+n)%n,it[(i-1+n)%n]);
			ans=1;
			break;
		}
	}
	if(ans==0){
		cout<<"NE"<<endl;
	}
	





	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50