Submission #836663

#TimeUsernameProblemLanguageResultExecution timeMemory
836663nigusPaint By Numbers (IOI16_paint)C++17
80 / 100
2086 ms2068 KiB
#include "paint.h" #include <cstdlib> #include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vi; typedef vector<ll> vl; const int MAXN = 200004; const int MAXK = 104; vi A; vi C; vi CSB, CSW; int n,k; bool DP[MAXK][MAXN] = {0}; int DPC[MAXK][MAXN] = {0}; int NEXTB[MAXN] = {0}; int wh(int lo, int hi){ if(lo > hi)return 0; return CSW[hi+1]-CSW[lo]; } int bl(int lo, int hi){ if(lo > hi)return 0; return CSB[hi+1]-CSB[lo]; } int CW[MAXN] = {0}; int CB[MAXN] = {0}; int ANS[MAXN] = {0}; string alf = "X_?"; std::string solve_puzzle(string s, vector<int> c) { n = sz(s); k = sz(c); C = c; rep(c1,0,n){ if(s[c1] == 'X'){ // black A.push_back(0); } if(s[c1] == '_'){ // white A.push_back(1); } if(s[c1] == '.'){ A.push_back(2); } } for(int I = 0; I < n; I++){ if(A[I] != 2){ ANS[I] = A[I]; continue; } for(int ai = 0; ai < 2; ai++){ bool DEBUG = (ai == -1 && I == 4); A[I] = ai; CSB.clear(); CSW.clear(); CSB.push_back(0); CSW.push_back(0); rep(c1,0,n){ CSB.push_back(CSB.back() + (A[c1] == 0)); CSW.push_back(CSW.back() + (A[c1] == 1)); } rep(c1,0,n+1){ rep(c2,0,k+1){ DP[c2][c1] = 0; } } int nex = n; NEXTB[n] = n; for(int c1 = n-1; c1 >= 0; c1--){ if(A[c1] == 0)nex = c1; NEXTB[c1] = nex; } for(int i = n; i >= C[k-1]; i--){ if(i < n && A[i] == 0)break; DP[k][i] = ((wh(i-C[k-1],i-1) == 0)); } DPC[k][0] = 0; rep(c1,0,n+1){ DPC[k][c1+1] = (DPC[k][c1] + DP[k][c1]); } for(int j = k-1; j >= 0; j--){ int c0 = 0; if(j > 0){ c0 = C[j-1]; } for(int i = c0+(j > 0); i < n; i++){ if(j == 0 || (A[i-1] != 0 && wh(i-1-c0,i-2) == 0)){ int lo = i + C[j] + (j < k-1); int hi = NEXTB[i] + C[j] + (j < k-1); if(DEBUG && i == 6){ cerr << j << " - " << wh(i-1-c0,i-2) << " what\n"; } hi = min(hi, n); if(lo <= hi){ DP[j][i] = (DPC[j+1][hi+1] - DPC[j+1][lo] > 0); } } } DPC[j][0] = 0; rep(c1,0,n+1){ DPC[j][c1+1] = (DPC[j][c1] + DP[j][c1]); } } if(DEBUG){ rep(c1,0,k+1){ rep(c2,0,n+1){ cerr << DP[c1][c2] << " "; } cerr << "\n"; } } if(DP[0][0]){ ANS[I] ^= (ai+1); } } ANS[I]--; A[I] = 2; } /* vector<pii> intervals; intervals.push_back({0,0}); rep(j,0,k){ sort(all(intervals)); vector<pii> intervals2; int r = 0; trav(p, intervals){ rep(i, max(r, p.first), p.second+1){ if(DP[j][i]){ } r = max(r, p.second+1); } } } */ string ans = ""; rep(c1,0,n){ //cerr << ANS[c1] << "\n"; ans += alf[ANS[c1]]; } 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...