oj.uz

Submission #47168

# Submission time Handle Problem Language Result Execution time Memory
47168 2018-04-28T13:23:17 Z Kmcode DEL13 (info1cup18_del13) C++14
100 / 100
 29 ms 1704 KB 
#include "bits/stdc++.h"
using namespace std;

#define MAX 100002

int n;

vector<int> v;
int q;

vector<pair<int, int> > vv;


bool ng;

vector<int> ope;
vector<int> v2;

bool dp[MAX][5];
int pr[MAX][5];
int rest[MAX][5];

void er() {
	v2.clear();
	for (int i = 0; i < vv.size(); i++) {
		v2.push_back(vv[i].second - vv[i].first + 1);
	}
	for (int i = 0; i <= v2.size(); i++) {
		for (int j = 0; j < 5; j++) {
			dp[i][j] = false;
		}
	}
	dp[0][0] = true;
	pr[0][0] = 0;
	for (int i = 0; i < v2.size(); i++) {
		vector<int> tmp;
		int num = v2[i];
		while (num > 2) {
			tmp.push_back(num);
			num -= 2;
		}
		tmp.push_back(num);
		reverse(tmp.begin(), tmp.end());
		int lim = min(5, (int)tmp.size());
		for (int j = 0; j < 5; j++) {
			for (int k = 0; k < lim; k++) {
				int lef = j;
				if (dp[i][j] == false)continue;
				int rig = tmp[k];
				if (lef > rig)continue;
				rig -= lef;
				if (rig < 5) {
					rest[i + 1][rig] = tmp[k];
					dp[i + 1][rig] = true;
					pr[i + 1][rig] = j;
				}
			}
		}
	}
	ng |= (dp[v2.size()][0] ^ true);
	if (ng == false) {
		int cur = 0;
		vector<int> tmp;
		for (int i = v2.size() - 1; i >= 0; i--) {
			{
				int z = pr[i+1][cur];
				while (z--) {
					tmp.push_back(vv[i].first - 1);
				}
			}
			vector<int> ar;
			for (int i2 = vv[i].first; i2 <= vv[i].second; i2++) {
				ar.push_back(i2);
			}
			while (ar.size() > rest[i+1][cur]) {
				int a = ar.back();
				ar.pop_back();
				int b = ar.back();
				ar.pop_back();
				int c = ar.back();
				ar.pop_back();
				tmp.push_back(b);
				ar.push_back(b);
			}
			cur = pr[i+1][cur];
		}
		reverse(tmp.begin(), tmp.end());
		for (int el : tmp) {
			ope.push_back(el);
		}
	}
	vv.clear();
	return;
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		ope.clear();
		ng = false;
		scanf("%d%d", &n,&q);
		v.clear();
		v.push_back(0);
		for (int i = 0; i < q; i++) {
			int a;
			scanf("%d", &a);
			v.push_back(a);
		}
		v.push_back(n+1);
		v.push_back(n + 2);
		for (int i = 1; i < v.size(); i++) {
			if (v[i] - v[i - 1] - 1 == 0) {
				er();
				continue;
			}
			vv.push_back(make_pair(v[i - 1] + 1, v[i] - 1));
		}
		if (ng) {
			puts("-1");
		}
		else {
			cout << ope.size() << endl;
			bool out = false;
			for (int el : ope) {
				if (out) {
					printf(" ");
				}
				out = true;
				printf("%d", el);
			}
			puts("");
		}
	}

	return 0;
}

Compilation message

del13.cpp: In function 'void er()':
del13.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= v2.size(); i++) {
                  ~~^~~~~~~~~~~~
del13.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v2.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (ar.size() > rest[i+1][cur]) {
           ~~~~~~~~~~^~~~~~~~~~~~~~~~
del13.cpp:76:9: warning: unused variable 'a' [-Wunused-variable]
     int a = ar.back();
         ^
del13.cpp:80:9: warning: unused variable 'c' [-Wunused-variable]
     int c = ar.back();
         ^
del13.cpp: In function 'int main()':
del13.cpp:112:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < v.size(); i++) {
                   ~~^~~~~~~~~~
del13.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n,&q);
   ~~~~~^~~~~~~~~~~~~~~
del13.cpp:107:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 13 ms 460 KB Output is correct
4 Correct 21 ms 468 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 664 KB Output is correct
2 Correct 4 ms 808 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 13 ms 460 KB Output is correct
4 Correct 21 ms 468 KB Output is correct
5 Correct 3 ms 808 KB Output is correct
6 Correct 3 ms 808 KB Output is correct
7 Correct 3 ms 808 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 13 ms 460 KB Output is correct
4 Correct 21 ms 468 KB Output is correct
5 Correct 3 ms 808 KB Output is correct
6 Correct 3 ms 808 KB Output is correct
7 Correct 3 ms 808 KB Output is correct
8 Correct 26 ms 948 KB Output is correct
9 Correct 18 ms 1024 KB Output is correct
10 Correct 18 ms 1024 KB Output is correct
11 Correct 29 ms 1704 KB Output is correct