Submission #878901

#TimeUsernameProblemLanguageResultExecution timeMemory
878901AsymmetryPaint By Numbers (IOI16_paint)C++17
7 / 100
1 ms600 KiB
#include<bits/stdc++.h> using namespace std; using LL=long long; #define FOR(i,l,r)for(int i=(l);i<=(r);++i) #define REP(i,n)FOR(i,0,(n)-1) #define ssize(x)int(x.size()) #ifdef DEBUG auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";} auto&operator<<(auto&o,auto x){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";} #define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X) #else #define debug(...){} #endif enum Cell { BLACK, WHITE, EMPTY }; auto&operator<<(auto&o,Cell x) { return o<<int(x); } string solve_puzzle(string s, vector<int> c) { int n = ssize(s); int k = ssize(c); debug(n, k); debug(s); debug(c); auto calc = [&](vector<Cell> t) { vector dp(n + 1, vector(k + 1, 0)); t.insert(t.begin(), EMPTY); t.emplace_back(EMPTY); debug("calc", t); vector<int> pref(n + 1), pref_black(n + 1); FOR (i, 1, n) { pref[i] = pref[i - 1] + (t[i] != WHITE); pref_black[i] = pref_black[i - 1] + (t[i] == BLACK); } debug(pref); dp[0][0] = 1; FOR (i, 1, n) { if (t[i] != BLACK) dp[i] = dp[i - 1]; if (t[i] == WHITE) continue; if (c[0] <= i && (pref[i] - pref[i - c[0]]) == c[0] && pref_black[i - c[0]] == 0) dp[i][1] = 1; FOR (j, 1, k - 1) if (c[j] < i && (pref[i] - pref[i - c[j]]) == c[j] && t[i - c[j]] != BLACK) dp[i][j + 1] |= dp[i - c[j] - 1][j]; } debug(dp); return dp; }; vector<Cell> t(n); REP (i, n) { if (s[i] == 'X') t[i] = BLACK; if (s[i] == '_') t[i] = WHITE; if (s[i] == '.') t[i] = EMPTY; } auto pref = calc(t); reverse(c.begin(), c.end()); auto suff = calc(vector(t.rbegin(), t.rend())); reverse(c.begin(), c.end()); suff.emplace_back(suff.back()); reverse(suff.begin(), suff.end()); suff.emplace_back(suff.back()); debug(pref); debug(suff); string ans = s; vector<int> can_be_white(n); FOR (i, 1, n) REP (j, k + 1) if (pref[i - 1][j] && suff[i + 1][k - j]) can_be_white[i - 1] = 1; vector<int> can_be_black(n + 1); t.insert(t.begin(), EMPTY); t.emplace_back(EMPTY); vector sum(n + 1, 0), sum_black(n + 1, 0); FOR (i, 1, n) { sum[i] = sum[i - 1] + (t[i] != WHITE); sum_black[i] = sum_black[i - 1] + (t[i] == BLACK); } REP (j, k) { FOR (i, c[j], n) { if ((i == c[j]) && j) continue; if (j == 0) { /* if (j == k - 1) { if ((sum[i] - sum[i - c[j]]) == c[j] && sum_black[i - c[j]] == 0 && sum_black[n] == sum_black[i]) { debug("add", j, i, i - c[j], i); ++can_be_black[i - c[j]]; --can_be_black[i]; } } else if ((sum[i] - sum[i - c[j]]) == c[j] && sum_black[i - c[j]] == 0 && t[i + 1] != BLACK && suff[i + 2][k - 1]) { debug("add", j, i, i - c[j], i); ++can_be_black[i - c[j]]; --can_be_black[i]; } */ if ((sum[i] - sum[i - c[j]]) == c[j] && sum_black[i - c[j]] == 0 && t[i + 1] != BLACK && suff[i + 2][k - 1]) { debug("add", j, i, i - c[j], i); ++can_be_black[i - c[j]]; --can_be_black[i]; } } else if (j == k - 1) { if ((sum[i] - sum[i - c[j]]) == c[j] && sum_black[n] == sum_black[i] && t[i - c[j]] != BLACK && pref[i - c[j] - 1][j]) { debug(j, i); ++can_be_black[i - c[j]]; --can_be_black[i]; } } else { if ((sum[i] - sum[i - c[j]]) == c[j] && t[i - c[j]] != BLACK && t[i + 1] != BLACK && pref[i - c[j] - 1][j] && suff[i + 2][k - j - 2]) { debug(j, i); ++can_be_black[i - c[j]]; --can_be_black[i]; } } } } FOR (i, 1, n - 1) can_be_black[i] += can_be_black[i - 1]; REP (i, n) { if (t[i + 1] == BLACK) can_be_white[i] = 0; if (t[i + 1] == WHITE) can_be_black[i] = 0; } debug(can_be_black); debug(can_be_white); REP (i, n) { if (!can_be_black[i]) ans[i] = '_'; else if (!can_be_white[i]) ans[i] = 'X'; else ans[i] = '?'; } return ans; } #ifdef LOCAL int main() { cin.tie(0)->sync_with_stdio(0); int k; cin >> k; vector<int> c(k); REP (i, k) cin >> c[i]; string s; cin >> s; cout << solve_puzzle(s, c) << endl; } #endif

Compilation message (stderr)

paint.cpp:20:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | auto&operator<<(auto&o,Cell x) {
      |                 ^~~~
#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...