oj.uz

Submission #96494

# Submission time Handle Problem Language Result Execution time Memory
96494 2019-02-09T17:59:33 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[300000];
vector<int> seq[300000];
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 267 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 873 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 267 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 873 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 237 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 231 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 16 ms 15096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 15 ms 15100 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 267 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 873 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 237 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 231 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 14 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 16 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 16 ms 15096 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 267 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 873 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 237 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 231 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 14 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 16 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 16 ms 15096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 14 ms 15212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 14 ms 15096 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 13 ms 14584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 14 ms 14840 KB Execution killed with signal 11 (could be triggered by violating memory limits)