oj.uz

답안 #227529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
227529 2020-04-27T17:14:13 Z kshitij_sodani Trobojnica (COCI19_trobojnica) C++17
0 / 110
 11 ms 12160 KB 
#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.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 12160 KB Output isn't correct
2 Halted 0 ms 0 KB -