oj.uz

Submission #127378

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

	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 Incorrect 3 ms 376 KB Output isn't correct

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Incorrect 16 ms 608 KB Output isn't correct
4 Incorrect 18 ms 632 KB Output isn't correct

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 14840 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 Incorrect 3 ms 376 KB Output isn't correct
3 Incorrect 16 ms 608 KB Output isn't correct
4 Incorrect 18 ms 632 KB Output isn't correct
5 Incorrect 25 ms 1144 KB Output isn't correct
6 Incorrect 31 ms 1144 KB Output isn't correct
7 Incorrect 25 ms 1120 KB Output isn't correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Incorrect 16 ms 608 KB Output isn't correct
4 Incorrect 18 ms 632 KB Output isn't correct
5 Incorrect 25 ms 1144 KB Output isn't correct
6 Incorrect 31 ms 1144 KB Output isn't correct
7 Incorrect 25 ms 1120 KB Output isn't correct
8 Runtime error 28 ms 15556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 43 ms 15684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 816 ms 21308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 112 ms 15480 KB Execution killed with signal 11 (could be triggered by violating memory limits)