Submission #295894

#TimeUsernameProblemLanguageResultExecution timeMemory
295894erd1Paint By Numbers (IOI16_paint)C++14
80 / 100
2118 ms488184 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int N = 200000 + 2; bitset<N> targB, targW; array<vector<bitset<N>>, 2> dpB, dpW; array<vector<bool>, 2> valid; string solve_puzzle(string s, vector<int> c) { int k = c.size(), n = s.size(); if(n > N)return ""; for(int i = 0; i < n; i++)targB[i+2] = s[i] == 'X', targW[i+2] = s[i] == '_'; for(auto& i: dpB)i.resize(n+2); for(auto& i: dpW)i.resize(n+2); for(auto& i: valid)i.resize(n+2); auto stringify = [n](int x, int y){ string ans = ""; if(!valid[x][y])return (string)"INVALID"; for(int i = 2; i < n+2; i++){ //assert(dpW[n][k][i] || dpB[n][k][i]); if(dpW[x][y][i] && dpB[x][y][i]) ans += '?'; else if(dpW[x][y][i]) ans += '_'; else if(dpB[x][y][i]) ans += 'X'; else ans += '!'; } return ans; }; valid[0][0] = 1; for(int i = 1; i <= n+1; i++){ valid[0][i] = 1, dpW[0][i] = dpW[0][i-1]; dpW[0][i][i] = 1; } //cout << "hi" << endl; for(int j = 1; j <= k; j++){ for(int i = 0; i < n+2; i++)dpW[j&1][i].reset(), dpW[j&1][i].reset(), valid[j&1][i] = 0; for(int i = 2; i < n+2; i++){ if(i <= c[j-1] || !valid[!(j&1)][i-c[j-1]-1]){ if(valid[j&1][i-1] && !targB[i]) dpW[j&1][i] = dpW[j&1][i-1], dpB[j&1][i] = dpB[j&1][i-1], dpW[j&1][i][i] = 1, valid[j&1][i] = 1; continue; } valid[j&1][i] = 1; dpW[j&1][i] = dpW[!(j&1)][i-c[j-1]-1]; dpB[j&1][i] = dpB[!(j&1)][i-c[j-1]-1]; //if(i != c[j-1]) dpW[j&1][i][i-c[j-1]] = 1; for(int x = i-c[j-1]+1; x <= i; x++)dpB[j&1][i][x] = 1; //cout << i-1 << " " << j << " " << stringify(i, j) << endl; if(((dpB[j&1][i] & targW) | (dpW[j&1][i] & targB)).count()) dpW[j&1][i] = dpW[j&1][i-1], dpB[j&1][i] = dpB[j&1][i-1], valid[j&1][i] = valid[j&1][i-1], dpW[j&1][i][i] = 1; else if(valid[j&1][i-1] && !targB[i]) dpW[j&1][i] |= dpW[j&1][i-1], dpB[j&1][i] |= dpB[j&1][i-1], dpW[j&1][i][i] = 1; if(dpW[j&1][i][i] && targB[i])valid[j&1][i] = 0, dpW[j&1][i][i] = 0; //cout << i-1 << " " << j << " " << stringify(i, j) << endl; } } return stringify(k&1, n+1); }
#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...