제출 #275516

#제출 시각아이디문제언어결과실행 시간메모리
275516ggoorooPaint By Numbers (IOI16_paint)C++14
90 / 100
2096 ms184500 KiB
#include "paint.h" #include <cstdlib> #include <vector> #include <cstdio> #include <iostream> #include <cstring> #define N 200005 using namespace std; int n, m, c[N], v[N][105][2], ans[N][2], ss[N], cnt[N], mx[N]; string a; int g(int p) { if (p < 0) return 0; return cnt[p]; } int f(int p, int q, int z) { int t, ch = 0, cch = 0, pl; if (p >= n) { if (q == m) return 1; return 0; } if (v[p][q][z] != -1) return v[p][q][z]; pl = c[q + 1]; if (q < m && p + pl - 1 < n && g(p + pl - 1) - g(p - 1) == 0 && z == 0 && a[p + pl] != 'X') { t = f(p + pl, q + 1, 1); if (t == 1) { ans[p][0] = 1; cch = 1; } } if (a[p] == '.' || a[p] == '_') { t = f(p + 1, q, 0); if (t == 1) { ans[p][1] = 1; ch = 1; } } if (cch) { mx[p] = max(mx[p], p + pl - 1); } // if ((a[p] == '.' || a[p] == 'X')) { // if (q + 1 < ss[w]) t = f(p + 1, q + 1, w, 0); // else t = f(p + 1, q + 1, w + 1, 1); // if (t == 1) { // ans[p][0] = 1; // ch = 1; // } // } // if ((a[p] == '.' || a[p] == '_') && !(z == 0 && q > ss[w - 1] && q < ss[w])) { // t = f(p + 1, q, w); // if (t == 1) { // ans[p][1] = 1; // ch = 1; // } // } return v[p][q][z] = (ch | cch); } std::string solve_puzzle(std::string s, std::vector<int> cc) { int i, la; a = s; n = a.size(); if (a[0] == '_') cnt[0] = 1; else cnt[0] = 0; for (i = 1; i < n; i++) cnt[i] = cnt[i - 1] + (a[i] == '_'); cnt[n] = cnt[n - 1]; m = cc.size(); for (i = 0; i < m; i++) { c[i + 1] = cc[i]; } for (i = 1; i <= m; i++) ss[i] = ss[i - 1] + c[i]; memset(v, -1, sizeof(v)); f(0, 0, 0); la = -1; bool vb, vw; for (i = 0; i < n; i++) { vb = vw = 0; if (ans[i][0]) la = max(la, mx[i]); if (ans[i][0]) vb = 1; if (la != -1 && i <= la) vb = 1; if (ans[i][1]) vw = 1; if (vb + vw == 2) { a[i] = '?'; } else if (vb + vw == 1) { if (vb == 1) a[i] = 'X'; else a[i] = '_'; } else a[i] = '?'; } return a; }
#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...