oj.uz

Submission #199428

# Submission time Handle Problem Language Result Execution time Memory
199428 2020-02-01T12:12:06 Z GSmerch DEL13 (info1cup18_del13) C++14
100 / 100
 59 ms 5680 KB 
#include <bits/stdc++.h>

typedef int ll;
typedef long double ld;


using namespace std;

#define fi first
#define se second
#define sz(x) (x).size()
#define pll pair<ll,ll >
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define endln '\n'
#define cont continue
#define sqr(x) (x) * (x)

const ll MaxN = 1e5 + 100;
const ll LogN = 20;
ll Inf = 9e18;
const ll dx[4] = { 0,1,0,-1 };
const ll dy[4] = { 1,0,-1,0 };

ll T, N, M;
ll Mt[MaxN];
ll dist[MaxN];
bool dp[MaxN][3];
bool used[MaxN][3];

ll DP(ll v, ll pref) {

	if (v > M) return dp[v][pref] = (((dist[v - 1] - pref) % 2 == 0) && (dist[v - 1] >= pref) && ((pref > 0) || (dist[v - 1] - pref == 0)));
	if (used[v][pref]) return dp[v][pref];
	used[v][pref] = 1;
	for (int i = 0;i<3;i++) {
		ll k = dist[v - 1] - pref - i;
		if ((k < 0) || ((i == 0) && (k > 0) && (pref == 0)) || (k % 2)) cont;
		dp[v][pref] |= DP(v + 1, i);
	}
	return dp[v][pref];

}
ll Pr[MaxN];
void findAns(ll v, ll pref) {
	if (v > M) return;
	for (int i = 0;i<3;i++) {
		ll k = dist[v - 1] - pref - i;
		if ((!dp[v+1][i]) || (k < 0) || ((i == 0) && (k > 0) && (pref == 0)) || (k % 2)) cont;
		Pr[v] = i;
		findAns(v+1, i);
		return;
	}
}

int main() {

#ifdef LOCAL
	ifstream cin("input.txt");
	ofstream cout("output.txt");
#else
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
#endif
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//cout << fixed << setprecision(10);

	cin >> T;
	while (T--) {
		cin >> N >> M;
		for (int i = 1;i<M + 1;i++) {
			cin >> Mt[i];
		}
		Mt[0] = 0;
		Mt[M + 1] = N + 1;
		bool f = 1;
		for (int i = 1;i <= M + 1;i++) {
			if (Mt[i - 1] > Mt[i]) f = 0;
			dist[i - 1] = Mt[i] - Mt[i - 1] - 1;
		}
		if (!f) {
			cout << -1 << endln;
			cont;
		}
		memset(dp, 0, sizeof(dp));
		memset(used, 0, sizeof(used));
		DP(1, 0);
		//cerr << 1 << endln;
		findAns(1, 0);
		vector<ll > Ans;
		if (dp[1][0]) {
			for (int i = 0;i<=M;i++) {
				ll s = Pr[i];
				ll e = Pr[i + 1];
				ll sz = Mt[i+1] - Mt[i] - 1;
				ll St = Mt[i] + 2;
				while (sz > s + e) {
					sz -= 2;
					Ans.pb(St);
					St += 2;
				}
			}
			for (int i = 1;i<=M;i++) {
				for (int j = 1;j<=Pr[i];j++) {
					Ans.pb(Mt[i]);
				}
			}
			cout << sz(Ans) << endln;
			for (ll a : Ans) cout << a << ' ';
			cout << endln;
		}
		else {
			cout << -1 << endln;
		}

	}

	return 0;
}

Compilation message

del13.cpp:22:10: warning: overflow in implicit constant conversion [-Woverflow]
 ll Inf = 9e18;
          ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 888 KB Output is correct
2 Correct 15 ms 888 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 888 KB Output is correct
2 Correct 15 ms 888 KB Output is correct
3 Correct 53 ms 1016 KB Output is correct
4 Correct 59 ms 1272 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1144 KB Output is correct
2 Correct 10 ms 1144 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 888 KB Output is correct
2 Correct 15 ms 888 KB Output is correct
3 Correct 53 ms 1016 KB Output is correct
4 Correct 59 ms 1272 KB Output is correct
5 Correct 8 ms 1020 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 7 ms 888 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 888 KB Output is correct
2 Correct 15 ms 888 KB Output is correct
3 Correct 53 ms 1016 KB Output is correct
4 Correct 59 ms 1272 KB Output is correct
5 Correct 8 ms 1020 KB Output is correct
6 Correct 7 ms 888 KB Output is correct
7 Correct 7 ms 888 KB Output is correct
8 Correct 17 ms 1912 KB Output is correct
9 Correct 18 ms 3192 KB Output is correct
10 Correct 16 ms 3320 KB Output is correct
11 Correct 24 ms 5680 KB Output is correct