oj.uz

Submission #127380

# Submission time Handle Problem Language Result Execution time Memory
127380 2019-07-09T09:47:26 Z E869120 DEL13 (info1cup18_del13) C++14
55 / 100
 500 ms 23340 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)

int col[1 << 18], cl[1 << 18], cr[1 << 18];
int dp[1009][1009], pres[1009][1009];

vector<int> solve(int N, vector<int>A) {
	if ((N - (int)A.size()) % 2 == 1) return vector<int>{-1};
	if (A.size() == 0) return vector<int>{-1};

	for (int i = 0; i <= N + 1; i++) {
		col[i] = -1; cl[i] = (1 << 30); cr[i] = -(1 << 30);
		for (int j = 0; j <= N + 1; j++) { dp[i][j] = 0; pres[i][j] = -1; }
	}

	dp[0][0] = 1;
	for (int i = 1; i <= A.size(); i++) {
		for (int j = 1; j <= N; j++) {
			for (int k = 0; k < j; k++) {
				if (dp[i - 1][k] == 0) continue;
				int el = k + 1, er = j;
				if (el == er && A[i - 1] != er) continue;
				if (el != er && !(el < A[i - 1] && A[i - 1] < er)) continue;
				if ((er - el) % 2 == 1) continue;

				dp[i][j] = 1;
				pres[i][j] = k;
			}
		}
	}

	if (dp[A.size()][N] == 0) return vector<int>{-1};

	int cy = N;
	for (int i = A.size(); i >= 1; i--) {
		for (int j = cy; j > pres[i][cy]; j--) col[j] = i;
		cy = pres[i][cy];
	}

	for (int i = 1; i <= N; i++) {
		if (col[i] == -1) continue;
		cl[col[i]] = min(cl[col[i]], i);
		cr[col[i]] = max(cr[col[i]], i);
	}

	for (int i = 1; i <= N; i++) {
		cl[col[i]] = min(cl[col[i]], i);
		cr[col[i]] = max(cr[col[i]], i);
	}

	vector<int>ans;
	for (int i = 1; i <= A.size(); i++) {
		if (cl[i] == cr[i]) continue;
		int lefthand = A[i - 1] - cl[i], righthand = cr[i] - A[i - 1];

		if (lefthand == 0 || righthand == 0) return vector<int>{-1};
		if ((cr[i] - cl[i]) % 2 == 1) return vector<int>{-1};

		if (lefthand <= righthand) {
			int mid = cr[i] - (righthand - lefthand) / 2;
			for (int j = 0; j < (righthand - lefthand) / 2; j++) ans.push_back(mid);
			for (int j = 0; j < lefthand; j++) ans.push_back(A[i - 1]);
		}
		if (lefthand > righthand) {
			int mid = cl[i] + (lefthand - righthand) / 2;
			for (int j = 0; j < (lefthand - righthand) / 2; j++) ans.push_back(mid);
			for (int j = 0; j < righthand; j++) ans.push_back(A[i - 1]);
		}
	}
	return ans;
}

int main() {
	int T; scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		int N1, V1; vector<int>A1;
		scanf("%d%d", &N1, &V1);
		for (int j = 1; j <= V1; j++) { int p; scanf("%d", &p); A1.push_back(p); }

		vector<int>L = solve(N1, A1);
		if (L == vector<int>{-1}) printf("-1\n");
		else {
			printf("%d\n", L.size());
			for (int j = 0; j < L.size(); j++) { if (j) printf(" "); printf("%d", L[j]); }
			printf("\n");
		}
	}
	return 0;
}

Compilation message

del13.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
del13.cpp: In function 'std::vector<int> solve(int, std::vector<int>)':
del13.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= A.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= A.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp: In function 'int main()':
del13.cpp:86:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
    printf("%d\n", L.size());
                   ~~~~~~~~^
del13.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < L.size(); j++) { if (j) printf(" "); printf("%d", L[j]); }
                    ~~^~~~~~~~~~
del13.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int T; scanf("%d", &T);
         ~~~~~^~~~~~~~~~
del13.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &N1, &V1);
   ~~~~~^~~~~~~~~~~~~~~~~~
del13.cpp:81:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for (int j = 1; j <= V1; j++) { int p; scanf("%d", &p); A1.push_back(p); }
                                          ~~~~~^~~~~~~~~~

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 376 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 376 KB Output is correct
3 Correct 15 ms 504 KB Output is correct
4 Correct 17 ms 504 KB Output is correct

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 22776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Correct 14 ms 1528 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 376 KB Output is correct
3 Correct 15 ms 504 KB Output is correct
4 Correct 17 ms 504 KB Output is correct
5 Correct 23 ms 1144 KB Output is correct
6 Correct 21 ms 1144 KB Output is correct
7 Correct 24 ms 1192 KB Output is correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 15 ms 504 KB Output is correct
4 Correct 17 ms 504 KB Output is correct
5 Correct 23 ms 1144 KB Output is correct
6 Correct 21 ms 1144 KB Output is correct
7 Correct 24 ms 1192 KB Output is correct
8 Runtime error 58 ms 22928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 99 ms 23008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 813 ms 23340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 368 ms 22776 KB Execution killed with signal 11 (could be triggered by violating memory limits)