Submission #674188

#	Time	Username	Problem	Language	Result	Execution time	Memory
674188		QwertyPi	DEL13 (info1cup18_del13)	C++14	0 / 100	128 ms	2168 KiB

del13

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 11;
const int B = 800;

int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

int n, m; 
bool in(int i, int j){
	return 0 <= i && i < n && 0 <= j && j < m;
}

int a[MAXN];
vector<int> ans;

vector<vector<int>> vvi;
void ko(int l, int r){
	if(l > r) vvi.push_back({});
	vector<int> vi;
	int tr = (r - l) / 2;
	for(int i = 0; i < tr; i++)
		ans.push_back((l + r) / 2);
	vi.push_back((l + r) / 2);
	if((l + r) % 2 == 1) vi.push_back(r);
	vvi.push_back(vi);
}

void solve(){
	ans.clear(); vvi.clear();
	int n, q; cin >> n >> q;
	if((n + q) % 2 || q == 0){
		cout << -1 << endl;
		return;
	}
	for(int i = 0; i < q; i++) cin >> a[i];
	sort(a, a + q);
	int l = 0, r = q - 1, c = 0;
	while(l < q && a[l] == l + 1) l++, c++;
	while(r >= 0 && a[r] == n - ((q - 1) - r)) r--, c++;
	vector<int> b;
	for(int i = l; i <= r; i++){
		b.push_back(a[i]);
	}
	q = b.size();
	for(int i = 0; i < q; i++){
		a[i] = b[i] - l;
	}
	n -= c;
	for(int i = 0; i < q - 1; i++){
		if(a[i] + 1 == a[i + 1]){
			cout << -1 << endl;
			return;
		}
	}
	if(q) ko(1, a[0] - 1), ko(a[q - 1] + 1, n);
	else ko(1, n);
	for(int i = 0; i < q - 1; i++){
		ko(a[i] + 1, a[i + 1] - 1);
	}

	for(int i = 0; i < q; i++){
		while(vvi[i].size() && vvi[i + 1].size()){
			ans.push_back(a[i]);
			vvi[i].pop_back();
			vvi[i + 1].pop_back();
		}
		if(vvi[i].size()){
			cout << -1 << endl;
			return;
		}
	}
	if(vvi[q].size()){
		cout << -1 << endl;
		return;
	}
	cout << ans.size() << endl;
	for(auto i : ans){
		cout << l + i << ' ';
	}
	cout << endl;
}

int32_t main(){
	int t; cin >> t;
	while(t--){
		solve();
	}
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25
• Subtask 5: 0 / 30