Submission #853355

#TimeUsernameProblemLanguageResultExecution timeMemory
853355hngwlogPaint By Numbers (IOI16_paint)C++14
90 / 100
367 ms524288 KiB
#include <bits/stdc++.h> #include "paint.h" using namespace std; #define fi first #define se second #define _size(x) (int)x.size() #define BIT(i, x) ((x >> i) & 1) #define MASK(n) ((1 << n) - 1) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; i++) #define FORD(i, a, b) for (int i = a, _b = (b); i >= _b; i--) #define FORB1(i, mask) for (int i = mask; i > 0; i ^= i & - i) #define FORB0(i, n, mask) for (int i = ((1 << n) - 1) ^ mask; i > 0; i ^= i & - i) #define FORALL(i, a) for (auto i: a) #define fastio ios_base::sync_with_stdio(0); cin.tie(0); string solve_puzzle(string s, vector<int> c) { int n = _size(s), k = _size(c); s = ' ' + s; vector<vector<int>> cnt(n + 1, vector<int>(2)); FOR(i, 1, n) { REP(type, 2) cnt[i][type] = cnt[i - 1][type]; if (s[i] == 'X') cnt[i][0]++; else if (s[i] == '_') cnt[i][1]++; } vector<vector<vector<short int>>> f(n + 1, vector<vector<short int>>(k + 1, vector<short int>(2))); f[0][0][1] = 1; FOR(i, 1, n) { FOR(j, 0, k) { REP(type, 2) { if ((s[i] == 'X' && type) || (s[i] == '_' && !type)) continue; if (s[i] == 'X') { if (!j) continue; if (i < c[j - 1] || cnt[i][1] - cnt[i - c[j - 1]][1]) continue; f[i][j][type] = max({f[i][j][type], f[i - c[j - 1]][j - 1][1]}); } else if (s[i] == '_') f[i][j][type] = max({f[i][j][type], f[i - 1][j][0], f[i - 1][j][1]}); else { f[i][j][1] = max({f[i][j][1], f[i - 1][j][0], f[i - 1][j][1]}); if (!j) continue; if (i < c[j - 1] || cnt[i][1] - cnt[i - c[j - 1]][1]) continue; f[i][j][0] = max({f[i][j][0], f[i - c[j - 1]][j - 1][1]}); } } } } FORD(i, n, 1) { FORD(j, k, 0) { REP(type, 2) { if (!f[i][j][type]) continue; if (j == k && cnt[n][0] - cnt[i][0] == 0) f[i][j][type]++; if (f[i][j][type] == 1) continue; if (type == 1) { if (f[i - 1][j][0] == 1) f[i - 1][j][0]++; if (f[i - 1][j][1] == 1) f[i - 1][j][1]++; } else if (f[i - c[j - 1]][j - 1][1] == 1) f[i - c[j - 1]][j - 1][1]++; } } } vector<int> _cnt(n + 2); FOR(i, 1, n) { FOR(j, 1, k) if (f[i][j][0] > 1) _cnt[i - c[j - 1] + 1]++, _cnt[i + 1]--; } FOR(i, 1, n) _cnt[i] += _cnt[i - 1]; string ans = ""; FOR(i, 1, n) { if (s[i] == 'X') ans += 'X'; else if (s[i] == '_') ans += '_'; else { int res = 0; FOR(j, 0, k) if (f[i][j][1] > 1) res++; if (_cnt[i]) { if (res) ans += '?'; else ans += 'X'; } else ans += '_'; } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...