oj.uz

Submission #127379

# Submission time Handle Problem Language Result Execution time Memory
127379 2019-07-09T09:44:17 Z E869120 DEL13 (info1cup18_del13) C++14
0 / 100
 500 ms 23384 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;
			}
		}
	}

	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:53: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:84: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:85: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:75: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:78: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:79: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
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Correct 3 ms 376 KB Output is correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 17 ms 504 KB Output isn't correct
4 Correct 18 ms 504 KB Output is correct

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 22864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 16 ms 1528 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 17 ms 504 KB Output isn't correct
4 Correct 18 ms 504 KB Output is correct
5 Correct 24 ms 1272 KB Output is correct
6 Correct 22 ms 1272 KB Output is correct
7 Correct 23 ms 1144 KB Output is correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 17 ms 504 KB Output isn't correct
4 Correct 18 ms 504 KB Output is correct
5 Correct 24 ms 1272 KB Output is correct
6 Correct 22 ms 1272 KB Output is correct
7 Correct 23 ms 1144 KB Output is correct
8 Runtime error 58 ms 23004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 97 ms 22904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 927 ms 23384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 360 ms 23032 KB Execution killed with signal 11 (could be triggered by violating memory limits)