oj.uz

Submission #96493

# Submission time Handle Problem Language Result Execution time Memory
96493 2019-02-09T17:58:58 Z KLPP DEL13 (info1cup18_del13) C++14
0 / 100
 500 ms 132096 KB 
#include<bits/stdc++.h>
 
using namespace std;
int n;
bool done;
bool possible[1000000];
vector<int> seq[1000000];
void DFS(int mask){
	if(possible[mask])return;
	possible[mask]=true;
	int arr[n];
	for(int i=0;i<n;i++){
		arr[i]=((mask&(1<<i))>0);
	}
	int prev[n];
	int next[n];
	prev[0]=-1;
	for(int i=1;i<n;i++){
		if(arr[i-1]==1)prev[i]=prev[i-1];
		else prev[i]=i-1;
	}
	next[n-1]=n;
	for(int i=n-2;i>-1;i--){
		if(arr[i+1]==1)next[i]=next[i+1];
		else next[i]=i+1;
	}
	/*for(int i=0;i<n;i++){
		cout<<prev[i]<<" "<<next[i]<<endl;
	}*/
	for(int i=0;i<n;i++){
		if(arr[i]==0 && prev[i]!=-1 && next[i]!=n){
			int less=(1<<prev[i])+(1<<next[i]);
			if(!possible[mask+less]){
				for(int j=0;j<seq[mask].size();j++)seq[mask+less].push_back(seq[mask][j]);
				seq[mask+less].push_back(i);
				DFS(mask+less);
			}
		}
	}
}

int main(){
	int t;
	cin>>t;
	done=false;
	while(t--){
		cin>>n;
		if(!done){
			for(int i=0;i<(1<<n);i++)possible[i]=false;
			DFS(0);
			/*for(int mask=0;mask<(1<<n);mask++){
				for(int i=0;i<n;i++)cout<<((mask&(1<<i))>0);
				cout<<" "<<possible[mask]<<endl;
			}*/
		}
		int l;
		cin>>l;
		int MSK=(1<<n)-1;
		for(int i=0;i<l;i++){
			int x;
			cin>>x;
			x--;
			MSK-=(1<<x);
		}
		if(possible[MSK]){
			cout<<seq[MSK].size()<<endl;
			for(int i=0;i<seq[MSK].size();i++)cout<<seq[MSK][i]+1<<" ";
			cout<<endl;
		}
		else cout<<-1<<endl;
	}	
	return 0;
}

Compilation message

del13.cpp: In function 'void DFS(int)':
del13.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<seq[mask].size();j++)seq[mask+less].push_back(seq[mask][j]);
                 ~^~~~~~~~~~~~~~~~~
del13.cpp: In function 'int main()':
del13.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<seq[MSK].size();i++)cout<<seq[MSK][i]+1<<" ";
                ~^~~~~~~~~~~~~~~~

Subtask #1
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 750 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 750 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 231 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 212 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 49324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 44 ms 49320 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 750 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 231 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 212 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 46 ms 47480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 44 ms 47456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 44 ms 49288 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 750 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 231 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 212 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 46 ms 47480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 44 ms 47456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 44 ms 49288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 44 ms 49276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 43 ms 49336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 40 ms 47480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 45 ms 47864 KB Execution killed with signal 11 (could be triggered by violating memory limits)