oj.uz

Submission #127402

# Submission time Handle Problem Language Result Execution time Memory
127402 2019-07-09T10:28:55 Z E869120 DEL13 (info1cup18_del13) C++14
70 / 100
 51 ms 3128 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];
bool forced[1 << 18];

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); forced[i] = false;
	}

	if (N <= 100) {
		for (int i = 0; i <= N + 1; i++) {
			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];
		}
	}

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

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

			if (col[i] != col[i + 1]) {
				if (col[i] % 2 == A[col[i] - 1] % 2) forced[col[i]] = true;
				if (col[i + 1] % 2 == A[col[i + 1] - 1] % 2) forced[col[i + 1]] = true;
			}
		}
		if (A[0] == 1) forced[1] = true;
		if (A[A.size() - 1] == N) forced[A.size()] = true;

		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 < cl[1]; i++) col[i] = 1;
		for (int i = cr[A.size()] + 1; i <= N; i++) col[i] = A.size();

		for (int i = 1; i <= (int)A.size() - 1; i++) {
			int el = cr[i] + 1, er = cl[i + 1] - 1;
			if (forced[i] == true) { for (int j = el; j <= er; j++) col[j] = i + 1; }
			else if (forced[i + 1] == true) { for (int j = el; j <= er; j++) col[j] = i; }
			else {
				for (int j = el; j <= (el + er) / 2; j++) col[j] = i;
				for (int j = (el + er) / 2 + 1; j <= er; j++) col[j] = i + 1;
			}
		}
	}

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

	for (int i = 1; i <= A.size(); i++) {
		if (cr[i] >= cl[i + 1]) return vector<int>{-1};
	}

	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:24:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i <= A.size(); i++) {
                   ~~^~~~~~~~~~~
del13.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < A.size(); i++) {
                   ~~^~~~~~~~~~
del13.cpp:95:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= A.size(); i++) {
                  ~~^~~~~~~~~~~
del13.cpp:100: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:131: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:132: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:122: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:125: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:126: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 508 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 508 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 16 ms 504 KB Output is correct
4 Correct 18 ms 504 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1400 KB Output is correct
2 Correct 7 ms 1016 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 16 ms 504 KB Output is correct
4 Correct 18 ms 504 KB Output is correct
5 Correct 26 ms 1200 KB Output is correct
6 Correct 24 ms 1144 KB Output is correct
7 Correct 25 ms 1200 KB Output is correct

Subtask #5
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 16 ms 504 KB Output is correct
4 Correct 18 ms 504 KB Output is correct
5 Correct 26 ms 1200 KB Output is correct
6 Correct 24 ms 1144 KB Output is correct
7 Correct 25 ms 1200 KB Output is correct
8 Incorrect 42 ms 1400 KB Output isn't correct
9 Incorrect 44 ms 1584 KB Output isn't correct
10 Incorrect 43 ms 1944 KB Output isn't correct
11 Incorrect 51 ms 3128 KB Output isn't correct