제출 #836728

#제출 시각아이디문제언어결과실행 시간메모리
836728TigerpantsPaint By Numbers (IOI16_paint)C++17
0 / 100
64 ms79308 KiB
#include "paint.h" #include <iostream> #include <vector> #include <map> #include <set> #include <numeric> #include <functional> #include <algorithm> #include <cstdlib> #include <string> using namespace std; typedef long long int ll; typedef vector<ll> vll; typedef vector<vll> vvll; typedef pair<ll, ll> pll; typedef vector<pll> vpll; typedef pair<bool, bool> pbo; typedef vector<pbo> vpbo; typedef vector<bool> vb; const ll MAXN = 200000; const ll MAXK = 100; #define rep(i, a, b) for (ll i = a; i < b; i++) #define sz(a) (ll) a.size() #define pb(a) push_back(a) #define mp(a, b) make_pair(a, b) #define trav(i, a, t) for (t::iterator i = a.begin(); i != a.end(); i++) ll n, k; vll c; bool fdp[MAXN + 1][MAXK + 1][2]; bool bdp[MAXN + 1][MAXK + 1][2]; vll white; // white[i] = #white in [0, i) vll black; // . . . bool inline no_white(ll l, ll r) { // check if interval [l, r] has no white return white[r + 1] == white[l]; // white[r + 1] == white[r] + P[r] = ... = P[r] + P[r - 1] + ... + P[l] + while[l] } bool inline no_black(ll l, ll r) { // check if interval [l, r] has no black return black[r + 1] == black[l]; } std::string solve_puzzle(std::string s, std::vector<int> c_) { //cout << "solve_puzzle" << endl; n = sz(s); k = sz(c_); c.resize(k); rep(i, 0, k) c[i] = c_[i]; //cout << "clear fdp bdp" << endl; rep(i, 0, MAXN + 1) { rep(j, 0, MAXK + 1) { fdp[i][j][0] = false; fdp[i][j][1] = false; bdp[i][j][0] = false; bdp[i][j][1] = false; } } //cout << "white & black" << endl; // prefix sum white.resize(n + 1); black.resize(n + 1); white[0] = 0; black[0] = 0; rep(i, 0, n) { white[i + 1] = white[i] + (s[i] == '_'); black[i + 1] = black[i] + (s[i] == 'X'); } //cout << "forward dp" << endl; fdp[0][0][1] = no_white(0, c[0] - 1); fdp[0][0][0] = no_black(0, 0); // do forward_dp rep(x, 1, n) { rep(i, 0, k) { if (x + c[i] <= n) { fdp[x][i][1] = fdp[x - 1][i][0] & no_white(x, x + c[i] - 1); } } // i == 0 fdp[x][0][0] = fdp[x - 1][0][0] & no_black(x, x); rep(i, 1, k + 1) { if (x >= c[i - 1]) { fdp[x][i][0] = (fdp[x - 1][i][0] | fdp[x - c[i - 1]][i - 1][1]) & no_black(x, x); } else { fdp[x][i][0] = fdp[x - 1][i][0] & no_black(x, x); } } /* rep(i, 0, k) { fdp[x][i][1] = fdp[x - 1][i][0] & no_white(x, x + c[i] - 1); fdp[x][i][0] = (fdp[x - 1][i][0] | fdp[x - c[i - 1]][i - 1][1]) & no_black(x, x); } */ } //cout << "backward dp" << endl; bdp[n - c[k - 1]][k - 1][1] = no_white(n - c[k - 1], n - 1); //bdp[n][k][0] = true; bdp[n - 1][k][0] = no_black(n - 1, n - 1); // do backward_dp for (ll x = n - 1; x >= 0; x--) { rep(i, 0, k) { if (x + c[i] <= n) { /* if ((x == 0) && (i == 0)) { cout << "here: " << bdp[x + c[i]][i + 1][0] << " " << no_white(x, x + c[i] - 1) << endl; } */ bdp[x][i][1] |= bdp[x + c[i]][i + 1][0] & no_white(x, x + c[i] - 1); } } rep(i, 0, k) { bdp[x][i][0] = (bdp[x + 1][i][0] | bdp[x + 1][i][1]) & no_black(x, x); } bdp[x][k][0] = bdp[x + 1][k][0] & no_black(x, x); /* rep(i, 0, k) { bdp[x][i][1] = bdp[x + c[i]][i + 1][0] & no_white(x, x + c[i] - 1); bdp[x][i][0] = (bdp[x + 1][i][0] | bdp[x + 1][i + 1][1]) & no_black(x, x); } */ } //cout << "compile possibilities" << endl; vb can_be_white(n, false); vb can_be_black(n, false); vll black_sweep(n, 0); rep(x, 0, n) { rep(i, 0, k + 1) { if (fdp[x][i][0] & bdp[x][i][0]) { can_be_white[x] = true; } if (fdp[x][i][1] & bdp[x][i][1]) { black_sweep[x]++; black_sweep[x + c[i]]--; } } } //cout << "sweep:" << endl; ll sweep = 0; rep(x, 0, n) { sweep += black_sweep[x]; can_be_black[x] = (sweep > 0); //cout << sweep << " "; } //cout << endl; //cout << "gen answer" << endl; string answ; rep(x, 0, n) { answ += can_be_white[x] ? (can_be_black[x] ? '?' : '_') : (can_be_black[x] ? 'X' : '.'); } //cout << answ << endl; /* cout << "fdp" << endl;; cout << "white:" << endl; rep(i, 0, k + 1) { rep(x, 0, n) { cout << fdp[x][i][0] << " "; } cout << endl; } cout << "black:" << endl; rep(i, 0, k + 1) { rep(x, 0, n) { cout << fdp[x][i][1] << " "; } cout << endl; } cout << "bdp" << endl;; cout << "white:" << endl; rep(i, 0, k + 1) { rep(x, 0, n) { cout << bdp[x][i][0] << " "; } cout << endl; } cout << "black:" << endl; rep(i, 0, k + 1) { rep(x, 0, n) { cout << bdp[x][i][1] << " "; } cout << endl; } */ return answ; }
#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...