Submission #1210233

#TimeUsernameProblemLanguageResultExecution timeMemory
1210233onbertPaint By Numbers (IOI16_paint)C++20
32 / 100
0 ms328 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5, maxk = 105, INF = 1e9; int n, k; bool dp[maxn][maxk][2]; int dpsum[maxn][maxk][2]; bool ansb[maxn], answ[maxn]; bool qry(int il, int ir, int j, int ii) { if (il > ir) return 0; if (ii == 0) { int val = dpsum[ir][j][ii]; if (il-1 >= 0) val -= dpsum[il-1][j][ii]; return val; } else if (ii == 1) { int val = dpsum[il][j][ii]; if (ir+1 <= n+1) val -= dpsum[ir+1][j][ii]; return val; } return 69420; } string solve_puzzle(string s, vector<int> c) { n = s.size(), k = c.size(); c.push_back(0); for (int i=k;i>=1;i--) swap(c[i-1], c[i]); s = '_' + s; int lastw[n+1], lastb[n+1]; lastw[0] = 0, lastb[0] = 0; for (int i=1;i<=n;i++) { lastw[i] = lastw[i-1], lastb[i] = lastb[i-1]; if (s[i] == 'X') lastb[i] = i; if (s[i] == '_') lastw[i] = i; } dp[0][0][0] = dpsum[0][0][0] = 1; for (int i=1;i<=k;i++) dp[0][i][0] = dpsum[0][i][0] = 0; for (int i=1;i<=n;i++) { int w = lastw[i]; dp[i][0][0] = (lastb[i] == 0); dpsum[i][0][0] = dpsum[i-1][0][0] + dp[i][0][0]; for (int j=1;j<=k;j++) { int pos = i - c[j]; dp[i][j][0] = (i - lastw[i] >= c[j] && (pos == 0 && j-1 == 0 || (qry(lastb[pos], pos - 1, j-1, 0)))); dpsum[i][j][0] = dp[i-1][j][0] + dp[i][j][0]; } } int nextb[n+2], nextw[n+2]; nextb[n+1] = nextw[n+1] = n+1; for (int i=n;i>=1;i--) { nextw[i] = nextw[i+1], nextb[i] = nextb[i+1]; if (s[i] == 'X') nextb[i] = i; if (s[i] == '_') nextw[i] = i; } dp[n+1][k+1][1] = dpsum[n+1][k+1][1] = 1; for (int i=1;i<=k;i++) dp[n+1][i][1] = dpsum[n+1][i][1] = 0; for (int i=n;i>=1;i--) { int w = nextw[i]; dp[i][k+1][1] = (nextb[i] == n+1); dpsum[i][k+1][1] = dpsum[i+1][k+1][1] + dp[i][k+1][1]; for (int j=1;j<=k;j++) { int pos = i + c[j]; dp[i][j][1] = (nextw[i] - i >= c[j] && (pos == n+1 && j+1 == k+1 || qry(pos + 1, nextb[pos], j+1, 1))); dpsum[i][j][1] = dp[i+1][j][1] + dp[i][j][1]; } } for (int i=1;i<=n;i++) for (int j=1;j<=k;j++) { if (i - c[j] + 1 >= 1) dp[i][j][0] &= dp[i - c[j] + 1][j][1]; dpsum[i][j][0] = dpsum[i-1][j][0] + dp[i][j][0]; } for (int i=n;i>=1;i--) for (int j=1;j<=k;j++) { if (i + c[j] - 1 <= n) dp[i][j][1] &= dp[i + c[j] - 1][j][0]; dpsum[i][j][1] = dpsum[i+1][j][1] + dp[i][j][1]; } for (int i=1;i<=n;i++) { answ[i] = ansb[i] = 0; for (int j=0;j<=k;j++) answ[i] |= (dpsum[i-1][j][0] && dpsum[i+1][j+1][1]); for (int j=1;j<=k;j++) ansb[i] |= qry(i, min(i + c[j] - 1, n), j, 0); } string ans; for (int i=1;i<=n;i++) { if (answ[i] && ansb[i]) ans += '?'; else if (answ[i]) ans += '_'; else if (ansb[i]) ans += 'X'; } return ans; }

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...