# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
758948 | 2023-06-15T15:03:05 Z | minhcool | Paint By Numbers (IOI16_paint) | C++17 | 4 ms | 7380 KB |
//#define local #ifndef local #include "paint.h" #endif #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; //#define int long long #define fi first #define se second #define pb push_back #define mp make_pair typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 3e5 + 5; const int oo = 1e18 + 7, mod = 1e9 + 7; mt19937 rng(1); int rnd(int l, int r){ int temp = rng() % (r - l + 1); return abs(temp) + l; } int pref0[N], pref1[N]; vector<int> okay[N]; int lst[105][N]; string solve_puzzle(string s, vector<int> c) { //return ""; int n = s.length(); s = '*' + s; for(int i = 1; i <= n; i++){ pref0[i] = (pref0[i - 1] + (s[i] == '_')); pref1[i] = (pref1[i - 1] + (s[i] == 'X')); } okay[0].pb(-1); for(int i = 1; i <= c.size(); i++){ int temp = c[i - 1]; int itr = -1; for(int j = 1; j <= n; j++){ itr = max(itr, 0); while(itr < okay[i - 1].size() && okay[i - 1][itr] < (j - temp)) itr++; itr--; if(itr < 0) continue; if(pref0[j] > pref0[okay[i - 1][itr]]) continue; if(pref1[j - temp] > pref1[okay[i - 1][itr]]) continue; okay[i].pb(j); lst[i][j] = okay[i - 1][itr]; //cout << i << " " << j << "\n"; } } // exit(0); assert(okay[c.size()].size()); int itr = okay[c.size()].back(); for(int i = itr + 1; i <= n; i++) s[i] = '_'; for(int i = c.size(); i >= 1; i--){ int temp = c[i - 1]; for(int j = itr; j > lst[i][itr]; j--){ if((itr - j) < c[i - 1]) s[j] = 'X'; else s[j] = '_'; } itr = lst[i][itr]; } return s.substr(1); } //#define local #ifdef local void process(){ string s; int n; cin >> s >> n; vector<int> v; while(n--){ int x; cin >> x; v.pb(x); } cout << solve_puzzle(s, v) << "\n"; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); process(); } #endif local
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7380 KB | char #0 differ - expected: '?', found: '_' |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7380 KB | char #0 differ - expected: '?', found: '_' |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7380 KB | char #0 differ - expected: '?', found: '_' |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7380 KB | char #0 differ - expected: '?', found: '_' |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7380 KB | char #0 differ - expected: '?', found: '_' |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7380 KB | char #0 differ - expected: '?', found: '_' |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 7380 KB | char #0 differ - expected: '?', found: '_' |
2 | Halted | 0 ms | 0 KB | - |