oj.uz

답안 #127474

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
127474 2019-07-09T12:02:01 Z E869120 DEL13 (info1cup18_del13) C++14
100 / 100
 54 ms 17812 KB 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)

int col[1 << 17], cl[1 << 17], cr[1 << 17]; vector<int> vec[1 << 17];

// (pos, 現在の値, 左端が A[i] か, 区間の長さの偶奇)
int dp[1 << 17][2][4]; pair<int, int> pres[1 << 17][2][4];

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); vec[i].clear();
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 4; k++) { dp[i][j][k] = 0; pres[i][j][k] = make_pair(-1, -1); }
		}
	}

	// 前処理
	for (int i = 1; i <= A.size(); i++) vec[A[i - 1]].push_back(i);
	for (int i = 1; i <= A.size() - 1; i++) {
		for (int j = A[i - 1] + 1; j <= A[i] - 1; j++) { vec[j].push_back(i); vec[j].push_back(i + 1); }
	}
	for (int i = 1; i < A[0]; i++) { vec[i].push_back(0); vec[i].push_back(1); }
	for (int i = A[A.size() - 1] + 1; i <= N; i++) { vec[i].push_back(A.size()); vec[i].push_back(A.size() + 1); }
	vec[0].push_back(0);

	// 計算
	dp[0][0][3] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < vec[i].size(); j++) {

			// dp[i][j] に向けての遷移
			for (int k = 0; k < vec[i - 1].size(); k++) {

				// パターン A : 小さくなるパターン
				if (vec[i - 1][k] > vec[i][j]) continue;

				// パターン B : 変化しないパターン
				if (vec[i - 1][k] == vec[i][j]) {
					if (dp[i - 1][k][0] == 1) { dp[i][j][2] = 1; pres[i][j][2] = make_pair(k, 0); }
					if (dp[i - 1][k][1] == 1) { dp[i][j][3] = 1; pres[i][j][3] = make_pair(k, 1); }
					if (dp[i - 1][k][2] == 1) { dp[i][j][0] = 1; pres[i][j][0] = make_pair(k, 2); }
					if (dp[i - 1][k][3] == 1) { dp[i][j][1] = 1; pres[i][j][1] = make_pair(k, 3); }
				}

				// パターン C : 変化し大きくなるパターン
				if (vec[i - 1][k] < vec[i][j]) {
					if (vec[i - 1].size() == 1 && vec[i].size() == 1) {
						// C-1 : 長さは 1 でなければならない、かつ今回も長さ 1 制限あり
						if (dp[i - 1][k][3] == 1) { dp[i][j][3] = 1; pres[i][j][3] = make_pair(k, 3); }
					}
					if (vec[i - 1].size() == 1 && vec[i].size() != 1) {
						// C-2 : 長さは 1 でなければならない、かつ今回も長さ 1 制限なし
						if (dp[i - 1][k][3] == 1) { dp[i][j][2] = 1; pres[i][j][2] = make_pair(k, 3); }
					}
					if (vec[i - 1].size() != 1 && vec[i].size() == 1) {
						// C-3 : 長さは 1 であってはならない、かつ今回も長さ 1 制限あり
						if (dp[i - 1][k][2] == 1) { dp[i][j][3] = 1; pres[i][j][3] = make_pair(k, 2); }
					}
					if (vec[i - 1].size() != 1 && vec[i].size() != 1) {
						// C-4 : 長さは 1 であってはならない、かつ今回も長さ 1 制限なし
						if (dp[i - 1][k][2] == 1) { dp[i][j][2] = 1; pres[i][j][2] = make_pair(k, 2); }
					}
				}
			}
		}
	}

	pair<int, int> cy = make_pair(-1, -1);
	if (vec[N].size() == 1) {
		if (dp[N][0][3] == 1) { cy = make_pair(0, 3); }
	}
	else {
		if (dp[N][0][2] == 1) { cy = make_pair(0, 2); }
	}
	if (cy == make_pair(-1, -1)) return vector<int>{-1};

	for (int i = N; i >= 1; i--) {
		col[i] = vec[i][cy.first];
		cy = pres[i][cy.first][cy.second];
	}

	// 答えを最後に求める
	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:25:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= A.size(); i++) vec[A[i - 1]].push_back(i);
                  ~~^~~~~~~~~~~
del13.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= A.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~~
del13.cpp:36:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < vec[i].size(); j++) {
                   ~~^~~~~~~~~~~~~~~
del13.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = 0; k < vec[i - 1].size(); k++) {
                    ~~^~~~~~~~~~~~~~~~~~~
del13.cpp:96: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:127: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:128: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:118: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:121: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:122: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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 13 ms 3448 KB Output is correct
4 Correct 14 ms 3576 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 4220 KB Output is correct
2 Correct 6 ms 3548 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 13 ms 3448 KB Output is correct
4 Correct 14 ms 3576 KB Output is correct
5 Correct 6 ms 3448 KB Output is correct
6 Correct 6 ms 3448 KB Output is correct
7 Correct 6 ms 3448 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3448 KB Output is correct
2 Correct 5 ms 3448 KB Output is correct
3 Correct 13 ms 3448 KB Output is correct
4 Correct 14 ms 3576 KB Output is correct
5 Correct 6 ms 3448 KB Output is correct
6 Correct 6 ms 3448 KB Output is correct
7 Correct 6 ms 3448 KB Output is correct
8 Correct 22 ms 5240 KB Output is correct
9 Correct 24 ms 6776 KB Output is correct
10 Correct 28 ms 9852 KB Output is correct
11 Correct 54 ms 17812 KB Output is correct