oj.uz

Submission #47163

# Submission time Handle Problem Language Result Execution time Memory
47163 2018-04-28T13:14:38 Z Kmcode DEL13 (info1cup18_del13) C++14
40 / 100
 15 ms 1032 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];
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;
	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) {
					dp[i + 1][rig] = true;
				}
			}
		}
	}
	ng |= (dp[v2.size()][0] ^ true);
	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:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i <= v2.size(); i++) {
                  ~~^~~~~~~~~~~~
del13.cpp:31:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v2.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp: In function 'int main()':
del13.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < v.size(); i++) {
                   ~~^~~~~~~~~~
del13.cpp:65: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:70:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 248 KB Output is partially correct
2 Partially correct 3 ms 484 KB Output is partially correct

Subtask #2
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 248 KB Output is partially correct
2 Partially correct 3 ms 484 KB Output is partially correct
3 Partially correct 10 ms 484 KB Output is partially correct
4 Partially correct 10 ms 484 KB Output is partially correct

Subtask #3
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 524 KB Output is partially correct
2 Partially correct 5 ms 828 KB Output is partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 248 KB Output is partially correct
2 Partially correct 3 ms 484 KB Output is partially correct
3 Partially correct 10 ms 484 KB Output is partially correct
4 Partially correct 10 ms 484 KB Output is partially correct
5 Partially correct 2 ms 828 KB Output is partially correct
6 Partially correct 2 ms 828 KB Output is partially correct
7 Partially correct 3 ms 828 KB Output is partially correct

Subtask #5
12.0 / 30.0

# Verdict Execution time Memory Grader output
1 Partially correct 3 ms 248 KB Output is partially correct
2 Partially correct 3 ms 484 KB Output is partially correct
3 Partially correct 10 ms 484 KB Output is partially correct
4 Partially correct 10 ms 484 KB Output is partially correct
5 Partially correct 2 ms 828 KB Output is partially correct
6 Partially correct 2 ms 828 KB Output is partially correct
7 Partially correct 3 ms 828 KB Output is partially correct
8 Partially correct 13 ms 908 KB Output is partially correct
9 Partially correct 11 ms 960 KB Output is partially correct
10 Partially correct 11 ms 960 KB Output is partially correct
11 Partially correct 15 ms 1032 KB Output is partially correct