oj.uz

Submission #127396

# Submission time Handle Problem Language Result Execution time Memory
127396 2019-07-09T10:20:27 Z E869120 DEL13 (info1cup18_del13) C++14
0 / 100
 352 ms 23540 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; }
	}

	if (N <= 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];
		}
	}

	else {
		for (int i = 1; i <= A.size(); i++) { col[A[i - 1]] = i; }
		int id = -1;
		for (int i = 2; i <= N; i++) {
			if (col[i - 1] == -1 && col[i] >= 0 && col[i + 1] == -1) id = col[i];
		}
		if (id == -1) return vector<int>{-1};

		for (int i = 1; i <= N; i++) { if (col[i] == -1) col[i] = id; }
	}

	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:21:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i <= A.size(); i++) {
                   ~~^~~~~~~~~~~
del13.cpp:46:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i <= A.size(); i++) { col[A[i - 1]] = i; }
                   ~~^~~~~~~~~~~
del13.cpp:62: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:93: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:94: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:84: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:87: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:88: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 2 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 2 ms 376 KB Output isn't correct
3 Incorrect 9 ms 632 KB Output isn't correct
4 Incorrect 9 ms 504 KB Output isn't correct

Subtask #3
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 22780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 5 ms 1536 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 2 ms 376 KB Output isn't correct
3 Incorrect 9 ms 632 KB Output isn't correct
4 Incorrect 9 ms 504 KB Output isn't correct
5 Incorrect 4 ms 1148 KB Output isn't correct
6 Incorrect 4 ms 1144 KB Output isn't correct
7 Incorrect 4 ms 1144 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 2 ms 376 KB Output isn't correct
3 Incorrect 9 ms 632 KB Output isn't correct
4 Incorrect 9 ms 504 KB Output isn't correct
5 Incorrect 4 ms 1148 KB Output isn't correct
6 Incorrect 4 ms 1144 KB Output isn't correct
7 Incorrect 4 ms 1144 KB Output isn't correct
8 Runtime error 57 ms 23092 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 91 ms 23160 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 181 ms 23540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 352 ms 22884 KB Execution killed with signal 11 (could be triggered by violating memory limits)