Submission #774904

#TimeUsernameProblemLanguageResultExecution timeMemory
774904CookiePaint By Numbers (IOI16_paint)C++14
80 / 100
2086 ms474508 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; ifstream fin("VNOICUP.INP"); ofstream fout("VNOICUP.OUT"); #define sz(a) (int)a.size() #define ll long long #define pb push_back #define forr(i, a, b) for(ll i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #include "paint.h" #include <cstdlib> #define pll pair<ll, ll> #define pii pair<int, int> const ld PI = 3.14159265359; #define ull unsigned long long using u128 = __uint128_t; //const int x[4] = {1, -1, 0, 0}; //const int y[4] = {0, 0, 1, -1}; const ll mod = 1e9 + 7; const int mxn = 1e6 + 5, mxq = 2e5 + 5, sq = 400, mxv = 15 * 10, pr = 31; const int base = (1 << 18); const ll inf = 2e9, neg = -69420; void add(int &a, int b){ a += b; if(a >= mod)a -= mod; } int dp[105][105][105]; bool vis[105 * 105 * 105]; vt<int>adj[105 * 105 * 105]; map<pair<pair<int, int>, int>, int>mp; string s; int coef(int i, int j, int k){ return(mp[make_pair(make_pair(i, j), k)]); } std::string solve_puzzle(std::string s, std::vector<int> c) { s += '_'; vt<int>a; forr(i, 0, sz(c)){ a.pb(c[i]); } int cnt = 0; dp[0][0][0] = 1; for(int i = 0; i <= sz(s); i++){ for(int j = 0; j <= sz(a); j++){ for(int k = 0; k <= a[j]; k++){ mp[{{i, j}, k}] = ++cnt; } } } for(int i = 0; i < sz(s); i++){ for(int j = 0; j <= sz(a); j++){ for(int k = 0; k <= a[j]; k++){ if(dp[i][j][k] == 0)continue; if(s[i] == '_' || s[i] == '.'){ if(k == 0){ add(dp[i + 1][j][0], dp[i][j][k]); adj[coef(i + 1, j, 0)].pb(coef(i, j, k)); }else if(j < sz(a) && k == a[j]){ add(dp[i + 1][j + 1][0], dp[i][j][k]); adj[coef(i + 1, j + 1, 0)].pb(coef(i, j, k)); } }if(s[i] == '.' || s[i] == 'X'){ if(j < sz(a) && k < a[j]){ add(dp[i + 1][j][k + 1], dp[i][j][k]); adj[coef(i + 1, j, k + 1)].pb(coef(i, j, k)); } } } } } queue<int>q; q.push(coef(sz(s), sz(a), 0)); vis[coef(sz(s), sz(a), 0)] = 1; while(!q.empty()){ int nw = q.front(); q.pop(); for(auto i: adj[nw]){ if(!vis[i]){ vis[i] = 1; q.push(i); } } } string res = ""; for(int i = 0; i < sz(s) - 1; i++){ bool ok1 = 0, ok2 = 0; for(int j = 0; j <= sz(a); j++){ for(int k = 0; k <= a[j]; k++){ if(!vis[coef(i, j, k)])continue; if(k == 0 && vis[coef(i + 1, j, 0)])ok1 = 1; if(j < sz(a) && a[j] == k && vis[coef(i + 1, j + 1, 0)])ok1 = 1; if(j < sz(a) && k < a[j] && vis[coef(i + 1, j, k + 1)])ok2 = 1; } } if(ok1 && ok2)res += '?'; else if(ok1)res += '_'; else res += 'X'; } 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...