oj.uz

Submission #674189

# Submission time Handle Problem Language Result Execution time Memory
674189 2022-12-23T12:13:54 Z QwertyPi DEL13 (info1cup18_del13) C++14
15 / 100
 15 ms 1868 KB 
#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;
	for(int i = 0; i < q; i++) cin >> a[i];
	if((n + q) % 2 || q == 0){
		cout << -1 << endl;
		return;
	}
	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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Incorrect 2 ms 212 KB Output isn't correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Incorrect 10 ms 320 KB Output isn't correct
4 Incorrect 9 ms 312 KB Output isn't correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 3 ms 340 KB Output is correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Incorrect 10 ms 320 KB Output isn't correct
4 Incorrect 9 ms 312 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 212 KB Output isn't correct
2 Incorrect 2 ms 212 KB Output isn't correct
3 Incorrect 10 ms 320 KB Output isn't correct
4 Incorrect 9 ms 312 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Incorrect 1 ms 212 KB Output isn't correct
7 Incorrect 1 ms 212 KB Output isn't correct
8 Incorrect 12 ms 596 KB Output isn't correct
9 Incorrect 15 ms 724 KB Output isn't correct
10 Incorrect 13 ms 880 KB Output isn't correct
11 Incorrect 14 ms 1868 KB Output isn't correct