Submission #836478

#TimeUsernameProblemLanguageResultExecution timeMemory
836478EllinorPaint By Numbers (IOI16_paint)C++14
59 / 100
1 ms340 KiB
#include <iostream> #include <vector> #include <queue> #include <string> #include <cmath> #include <cstdlib> #include <set> #include <iomanip> #include <limits> #include <map> #include <assert.h> #include <algorithm> #include <list> #include <iterator> #include <fstream> #include <random> #include <unordered_map> #include <array> //#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for (int i = (a); i < b; i++) #define rrep(i,a) for (int i = (a) - 1; i >= 0; i--) #define pb push_back #define all(x) x.begin(), x.end() typedef long long ll; typedef pair<bool, bool> pbb; // fast #include "paint.h" // ! #include <cstdlib> // vector<vector<int>> dp; // dp vector<pbb> alts; //vector<bool> white_alts, black_alts; int N, K; string S; vector<int> C; vector<int> white_inds; vector<int> black_start; // ? bool go(int nat, int kat) { //if (kat >= K) return true; if (nat >= N && kat >= K) return true; if (nat >= N) return false; if (dp[nat][kat] != -1) return bool(dp[nat][kat]); // ?? if (S[nat] == '_') { dp[nat][kat] = go(nat + 1, kat); } else if (S[nat] == 'X') { if (kat >= K) { dp[nat][kat] = false; } else { // when next white, nw_ind - nat >= C[kat] -> yay int wi; if (white_inds.size() == 0) wi = N; else if (nat > white_inds[white_inds.size() - 1]) wi = N; else { int wii = lower_bound(all(white_inds), nat) - white_inds.begin(); wi = white_inds[wii]; } if (wi - nat >= C[kat]) { dp[nat][kat] = go(nat + C[kat] + 1, kat + 1); // +1 !! if (dp[nat][kat]) { alts[nat + C[kat]].second = true; black_start[nat] = max(black_start[nat], C[kat]); } } else { dp[nat][kat] = false; } } } else if (S[nat] == '.') // { if (kat >= K) { bool b = false, w; w = go(nat + 1, kat); if (w) { alts[nat].second = true; } dp[nat][kat] = w; } else { bool b, w; // black ? int wi; if (white_inds.size() == 0) wi = N; else if (nat > white_inds[white_inds.size() - 1]) wi = N; else { int wii = lower_bound(all(white_inds), nat) - white_inds.begin(); wi = white_inds[wii]; } if (wi - nat >= C[kat]) { b = go(nat + C[kat] + 1, kat + 1); // +1 if (b) { alts[nat + C[kat]].second = true; black_start[nat] = max(black_start[nat], C[kat]); } } else b = false; w = go(nat + 1, kat); //assert(b || w); if (b || w) { if (b) alts[nat].first = true; if (w) alts[nat].second = true; } dp[nat][kat] = (b || w); } } return bool(dp[nat][kat]); } std::string solve_puzzle(std::string s, std::vector<int> c) { N = s.size(); K = c.size(); S = s; C = c; dp.assign(N, vector<int>(K + 1, -1)); alts.assign(N, make_pair(false, false)); black_start.assign(N, -1); rep(i,0,N) { if (S[i] == '_') white_inds.pb(i); } go(0,0); // int reach = -1; // inc rep(i,0,N) { if (black_start[i] != -1) reach = max(reach, i + black_start[i] - 1); if (i <= reach) alts[i].first = true; } string ret = ""; rep(i,0,N) { if (S[i] == '_') ret += '_'; else if (S[i] == 'X') ret += 'X'; else if (alts[i].first && alts[i].second) ret += '?'; else if (alts[i].first) ret += 'X'; else if (alts[i].second) ret += '_'; else { ret += 'X'; } } return ret; }

Compilation message (stderr)

paint.cpp: In function 'bool go(int, int)':
paint.cpp:102:18: warning: unused variable 'b' [-Wunused-variable]
  102 |             bool b = false, w;
      |                  ^
#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...