제출 #301352

#제출 시각아이디문제언어결과실행 시간메모리
301352williamMBDKPaint By Numbers (IOI16_paint)C++17
90 / 100
2091 ms89080 KiB
#include<bits/stdc++.h> #include "paint.h" #include <cstdlib> using namespace std; const int MN = 200000; int N, K; string S; vector<int> C; vector<vector<int>> dp (MN + 10, vector<int> (101, -1)); vector<bool> x (MN), w(MN); vector<int> pref (MN), pref2(MN); 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]){ for(int i = i1; i < N; i++){ if(w[i]) break; w[i] = 1; } } return dp[i1][i2]; } dp[i1][i2] = 0; for(int i = i1; i + C[i2] - 1 < N; i++){ int c = pref[i + C[i2] - 1] - (i == 0 ? 0 : pref[i-1]); bool b = c == 0; int t = i + C[i2]; if(b && (t == N || S[t] != 'X') && rec(i + C[i2] + 1, i2+1)){ if(t < N){ w[t] = 1; } for(int j = i; j < i + C[i2]; j++){ x[j] = 1; } for(int j = i1; j < i; j++){ w[j] = 1; } for(int j = i1; j <= i; j++){ dp[j][i2] = 1; } } if(S[i] == 'X') break; } //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'); } rec(0, 0); string res (N, '?'); 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; if(x[i] && !w[i]) res[i] = 'X'; else if(!x[i] && w[i]) 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...