oj.uz

답안 #317246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
317246 2020-10-29T07:51:53 Z Seanliu DEL13 (info1cup18_del13) C++14
30 / 100
 417 ms 1920 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
using namespace std;

const int maxN = 18;
int T, N, M, l2[1 << maxN], fromst[1 << maxN], del[1 << maxN];
bool pos[1 << maxN];

void solve(){
	cin >> M;
	vector<int> has, wok;
	has.resize(M);
	fill(pos, pos + (1 << N), false);
	for(int i = 0; i < M; i++){
		cin >> has[i];
		has[i]--;
	}
	queue<int> que;
	que.push((1 << N) - 1);
	pos[(1 << N) - 1] = true;
	int curst = 0;
	for(int x : has) curst ^= (1 << x);
	bool f = false;
	while(que.size()){
		if(f) break;
		int i = que.front();
		que.pop();
		vector<int>().swap(wok);	
		int x = i;
		while(x){
			wok.push_back(l2[(x & -x)]);
			x -= (x & -x);
		}
		//for(int x : wok) cout << x << " ";
		//cout << endl;
		if(wok.size() >= 3){
			for(int j = 1; j < wok.size() - 1; j++){
				int n = i ^ (1 << wok[j - 1]) ^ (1 << wok[j + 1]);
				if(pos[n] || ((n & curst) != curst)) continue;
				pos[n] = true;
				que.push(n);
				fromst[n] = i;
				del[n] = wok[j];
				if(n == curst){
					f = true;
					break;
				}
			}
		}

	}
		//cout << "curst = " << curst << endl;
	if(!pos[curst]){
		cout << -1 << endl;
		return;
	}
	vector<int> ans;
	vector<int>().swap(ans);
	while(curst != ((1 << N) - 1)){
		ans.push_back(del[curst]);
		curst = fromst[curst];
	}
	reverse(ans.begin(), ans.end());
	cout << ans.size() << endl;
	for(int x : ans) cout << x + 1 << " ";
	cout << endl;
}

void solve2(){
	cin >> M;
	bool has[100000];
	vector<int> ans;
	vector<int>().swap(ans);
	int x, cnt = 0;
	for(int i = 0; i < M; i++){
		cin >> x;
		x--;
		has[x] = true;
		cnt++;
	}
	int k = -1;
	for(int i = 1; i < N - 1; i++){
		if(has[i] && !has[i - 1] && !has[i + 1]){
			k = i;
		}
	}
	if(k == -1 && cnt != N){
		cout << -1 << endl;
		return;
	} else if(k == -1){
		cout << 0 << endl;
		return;
	}
	cout << "k = " << k << endl;
	deque<int> l, r;
	for(int i = k - 1; i >= 0 && !has[i]; i--){
		//cout << "i = " << i << endl;
		l.push_front(i);
	}
	for(int i = k + 1; i < N && !has[i]; i++){
		//cout << "i = " << i << endl;
		r.push_back(i);
	}
	while(l.size() > 2){
		int a = l.front();
		l.pop_front();
		int b = l.front();
		l.pop_front();
		int c = l.front();
		l.pop_front();
		ans.push_back(b);
		l.push_front(b);
	}
	while(r.size() > 2){
		int a = r.front();
		r.pop_front();
		int b = r.front();
		r.pop_front();
		int c = r.front();
		r.pop_front();
		ans.push_back(b);
		r.push_front(b);
	}
	if(l.size() != r.size()){
		cout << -1 << endl;
	}
	while(l.size()){
		l.pop_back();
		r.pop_back();
		ans.push_back(k);
	}
	cout << ans.size() << endl;
	for(int x : ans) cout << x << " ";
	cout << endl;
}

int main(){
	for(int i = 0; i < maxN; i++) l2[1 << i] = i;
	cin >> T;
	while(T--){
		cin >> N;
		if(N <= 18)
			solve();
		else solve2();
	}
}

Compilation message

del13.cpp: In function 'void solve()':
del13.cpp:40:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    for(int j = 1; j < wok.size() - 1; j++){
      |                   ~~^~~~~~~~~~~~~~~~
del13.cpp: In function 'void solve2()':
del13.cpp:108:7: warning: unused variable 'a' [-Wunused-variable]
  108 |   int a = l.front();
      |       ^
del13.cpp:112:7: warning: unused variable 'c' [-Wunused-variable]
  112 |   int c = l.front();
      |       ^
del13.cpp:118:7: warning: unused variable 'a' [-Wunused-variable]
  118 |   int a = r.front();
      |       ^
del13.cpp:122:7: warning: unused variable 'c' [-Wunused-variable]
  122 |   int c = r.front();
      |       ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 239 ms 1288 KB Output is correct
4 Correct 417 ms 1784 KB Output is correct

Subtask #3
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 1920 KB Expected integer, but "k" found
2 Incorrect 18 ms 1464 KB Expected integer, but "k" found

Subtask #4
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 239 ms 1288 KB Output is correct
4 Correct 417 ms 1784 KB Output is correct
5 Incorrect 2 ms 384 KB Expected integer, but "k" found
6 Incorrect 3 ms 896 KB Expected integer, but "k" found
7 Incorrect 3 ms 384 KB Expected integer, but "k" found

Subtask #5
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 239 ms 1288 KB Output is correct
4 Correct 417 ms 1784 KB Output is correct
5 Incorrect 2 ms 384 KB Expected integer, but "k" found
6 Incorrect 3 ms 896 KB Expected integer, but "k" found
7 Incorrect 3 ms 384 KB Expected integer, but "k" found
8 Incorrect 30 ms 1276 KB Expected integer, but "k" found
9 Incorrect 31 ms 512 KB Expected integer, but "k" found
10 Incorrect 31 ms 1024 KB Expected integer, but "k" found
11 Incorrect 27 ms 512 KB Expected integer, but "k" found