제출 #96658

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96658		KLPP	DEL13 (info1cup18_del13)	C++14	40 / 100	19 ms	1272 KiB

del13

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;

int mod(int x){
	if(x==0)return 0;
	if(x%2==1)return 1;
	return 2;
}
bool test(vector<int> v){
	/*for(int i=0;i<=v.size();i++){
		for(int j=0;j<3;j++)DP[i][j]=-1;
	}DP[0][0]=1;
	DP[0][1]=0;
	DP[0][2]=0;*/
	bool DP[v.size()+1];
	DP[0]=true;
	for(int i=1;i<=v.size();i++){
		DP[i]=false;
		int res=v[i-1];
		res=mod(res);
		//cout<<res<<"Y"<<endl;
		for(int j=i-2;j>-1;j--){
			res=v[j]-res;
			if(res>=0){
				res=mod(res);
				//cout<<res<<endl;
				if(res%2==0){
					DP[i]=DP[i]|DP[j];
				}
				if(res==0)j=-1;
			}else j=-1;
		}
	}
	return DP[v.size()];
}
int possible(int n,vector<int> v){
	vector<int> diff;
	for(int i=0;i<v.size()-1;i++){
		diff.push_back(v[i+1]-v[i]-1);
	}
	/*for(int i=0;i<diff.size();i++){
		cout<<diff[i]<<" ";
	}cout<<endl;*/
	int res=0;
	int sz=0;
	vector<int> c;
	for(int i=0;i<diff.size();i++){
		if(diff[i]!=0){
			/*sz++;
			res+=diff[i];
			res%=2;*/
			/*if(!c->empty() && c->top()==1 && diff[i]==1){
				c->pop();
				if(!test(c))return -1;
				while(!c->empty())c->pop();
			}else */c.push_back(diff[i]);
		}else{
			if(!test(c))return -1;
			c.clear();
		}
	}
	if(!test(c))return -1;
	return 0;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		int l;
		cin>>l;
		vector<int> seq(l+2);
		seq[0]=0;
		for(int i=1;i<=l;i++){
			cin>>seq[i];
		}seq[l+1]=n+1;
		int sol=possible(n,seq);
		cout<<sol<<endl;
		//if(sol==0)cout<<endl;
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

del13.cpp: In function 'bool test(std::vector<int>)':
del13.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<=v.size();i++){
              ~^~~~~~~~~~
del13.cpp: In function 'int possible(int, std::vector<int>)':
del13.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v.size()-1;i++){
              ~^~~~~~~~~~~
del13.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<diff.size();i++){
              ~^~~~~~~~~~~~
del13.cpp:46:6: warning: unused variable 'res' [-Wunused-variable]
  int res=0;
      ^~~
del13.cpp:47:6: warning: unused variable 'sz' [-Wunused-variable]
  int sz=0;
      ^~

• Subtask 1: 6 / 15
• Subtask 2: 6 / 15
• Subtask 3: 6 / 15
• Subtask 4: 10 / 25
• Subtask 5: 12 / 30