제출 #393971

#제출 시각아이디문제언어결과실행 시간메모리
393971arwaeystoamnegPaint By Numbers (IOI16_paint)C++17
80 / 100
2078 ms468 KiB
// EXPLOSION! #define _CRT_SECURE_NO_WARNINGS #include<bits/stdc++.h> #include<unordered_set> #include<unordered_map> #include<chrono> using namespace std; typedef pair<int, int> pii; typedef long long ll; typedef pair<ll, ll> pll; typedef long double ld; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pair<int, int>> vpi; typedef vector<pair<ll, ll>> vpll; #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define trav(a,x) for (auto& a: x) #define pb push_back #define mp make_pair #define rsz resize #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define f first #define s second #define cont continue #define endl '\n' //#define ednl '\n' #define test int testc;cin>>testc;while(testc--) #define pr(a, b) trav(x,a)cerr << x << b; cerr << endl; #define message cout << "Hello World" << endl; const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!! const ll linf = 4000000000000000000LL; const ll inf = 1000000007;//998244353 void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; } }void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; } void setIO(string s) { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef arwaeystoamneg if (sz(s)) { freopen((s + ".in").c_str(), "r", stdin); if (s != "test1") freopen((s + ".out").c_str(), "w", stdout); } #endif } #ifndef arwaeystoamneg #include "paint.h" #endif const int MAX = 200005; int n, k, prefix[MAX], b[101]; bitset<101>dp[MAX]; string a; int check() { F0R(i, n) { prefix[i + 1] = prefix[i] + (a[i] == '_'); } F0R(i, n + 1)F0R(j, k + 1)dp[i][j] = 0; dp[0][0] = 1; F0R(i, n) { F0R(j, k + 1) { if (!dp[i][j])continue; if (j != k) { if (i + b[j] > n)continue; // if all X if (prefix[i + b[j]] - prefix[i] == 0) { if (j == k - 1) dp[i + b[j]][j + 1] = 1; else if (a[i + b[j]] != 'X') dp[i + b[j] + 1][j + 1] = 1; } } // if _ if (a[i] != 'X') dp[i + 1][j] = 1; } } return dp[n][k]; } std::string solve_puzzle(std::string s, std::vector<int> c) { a = s; n = sz(s); k = sz(c); F0R(i, k)b[i] = c[i]; string res = ""; F0R(i, n) { if (s[i] == '.') { int ans = 0; a[i] = 'X'; if (check())ans++; a[i] = '_'; if (check())ans += 2; a[i] = '.'; if (ans == 0)assert(0); if (ans == 1)res.pb('X'); if (ans == 2)res.pb('_'); if (ans == 3)res.pb('?'); } else { res.pb(s[i]); } } return res; } #ifdef arwaeystoamneg const int S_MAX_LEN = 200 * 1000; char buf[S_MAX_LEN + 1]; int main() { setIO(""); assert(1 == scanf("%s", buf)); std::string s = buf; int c_len; assert(1 == scanf("%d", &c_len)); std::vector<int> c(c_len); for (int i = 0; i < c_len; i++) { assert(1 == scanf("%d", &c[i])); } std::string ans = solve_puzzle(s, c); printf("%s\n", ans.data()); return 0; } #endif
#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...