oj.uz

Submission #96658

# Submission time Handle Problem Language Result Execution time Memory
96658 2019-02-10T16:18:49 Z KLPP DEL13 (info1cup18_del13) C++14
40 / 100
 19 ms 1272 KB 
#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;
}

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 256 KB Output is partially correct
2 Partially correct 3 ms 256 KB Output is partially correct

Subtask #2
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 256 KB Output is partially correct
2 Partially correct 3 ms 256 KB Output is partially correct
3 Partially correct 11 ms 248 KB Output is partially correct
4 Partially correct 12 ms 376 KB Output is partially correct

Subtask #3
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 7 ms 376 KB Output is partially correct
2 Partially correct 5 ms 376 KB Output is partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 256 KB Output is partially correct
2 Partially correct 3 ms 256 KB Output is partially correct
3 Partially correct 11 ms 248 KB Output is partially correct
4 Partially correct 12 ms 376 KB Output is partially correct
5 Partially correct 4 ms 256 KB Output is partially correct
6 Partially correct 3 ms 352 KB Output is partially correct
7 Partially correct 3 ms 256 KB Output is partially correct

Subtask #5
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 256 KB Output is partially correct
2 Partially correct 3 ms 256 KB Output is partially correct
3 Partially correct 11 ms 248 KB Output is partially correct
4 Partially correct 12 ms 376 KB Output is partially correct
5 Partially correct 4 ms 256 KB Output is partially correct
6 Partially correct 3 ms 352 KB Output is partially correct
7 Partially correct 3 ms 256 KB Output is partially correct
8 Partially correct 15 ms 604 KB Output is partially correct
9 Partially correct 19 ms 940 KB Output is partially correct
10 Partially correct 17 ms 888 KB Output is partially correct
11 Partially correct 17 ms 1272 KB Output is partially correct