Submission #301387

#TimeUsernameProblemLanguageResultExecution timeMemory
301387williamMBDKPaint By Numbers (IOI16_paint)C++17
90 / 100
2029 ms106360 KiB
#include<bits/stdc++.h> #include "paint.h" #include <cstdlib> using namespace std; struct BIT{ int N; vector<int> arr; BIT(){} BIT(int n){ N = n + 1; arr = vector<int> (N); } void _u(int i, int val){ if(i < N) arr[i] += val; } void u(int a, int b){ a++; b++; _u(b+1,-1); _u(a,1); } void start(){ for(int i = 1; i < N; i++) arr[i] += arr[i-1]; } int q(int i){ i++; return arr[i]; } }; const int MN = 200000; int N, K; string S; vector<int> C; vector<vector<int>> dp (MN + 10, vector<int> (101, -1)); vector<int> pref (MN), pref2(MN); BIT bitx, bitw; int rec(int i1, int i2){ if(dp[i1][i2] != -1) return dp[i1][i2]; if(i2 == K){ dp[i1][i2] = 1; if(i1 >= N) return 1; int c = pref2[N-1] - (i1 == 0 ? 0 : pref2[i1-1]); dp[i1][i2] = c == 0; if(dp[i1][i2]){ bitw.u(i1,N-1); } return dp[i1][i2]; } dp[i1][i2] = 0; if(i1 + C[i2] - 1 >= N) return dp[i1][i2]; int c = pref[i1 + C[i2] - 1] - (i1 == 0 ? 0 : pref[i1-1]); int t = i1 + C[i2]; if(c == 0 && (t == N || S[t] != 'X') && rec(i1 + C[i2] + 1, i2+1)){ if(t < N){ bitw.u(t,t); } bitx.u(i1,i1+C[i2]-1); dp[i1][i2] = 1; } if(S[i1] != 'X' && rec(i1 + 1, i2)){ bitw.u(i1,i1); dp[i1][i2] = 1; } //cout << i1 << " " << i2 << " " << dp[i1][i2] << endl; return dp[i1][i2]; } string solve_puzzle(string _s, vector<int> _c) { //cout << "input: " << _s << endl; S = _s; C = _c; //for(auto e : C) cout << e << " "; //cout << endl; N = S.length(); K = C.size(); pref[0] = (S[0] == '_'); for(int i = 1; i < N; i++){ pref[i] = pref[i-1] + (S[i] == '_'); } pref2[0] = (S[0] == 'X'); for(int i = 1; i < N; i++){ pref2[i] = pref2[i-1] + (S[i] == 'X'); } bitx = BIT(N); bitw = BIT(N); rec(0, 0); string res (N, '?'); bitx.start(); bitw.start(); for(int i = 0; i < N; i++){ /*if(S[i] == 'X') x[i] = 1; else if(S[i] == '_') w[i] = 1; if(w[i] == 0 && x[i] == 0) w[i] = 1;*/ int tx = bitx.q(i); int tw = bitw.q(i); if(tx > 0 && tw == 0) res[i] = 'X'; else if(tx == 0 && tw > 0) res[i] = '_'; } return res; }
#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...