Submission #1224697

#TimeUsernameProblemLanguageResultExecution timeMemory
1224697maya_sPaint By Numbers (IOI16_paint)C++20
0 / 100
0 ms320 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; typedef int ll; ll dp[200200][110]; ll pref[200200][110]; pair<vector<ll>, vector<ll>> calc_l(ll n, ll k, vector<ll> &v, vector<ll> &c){ ll j = 0, cnt = 0, lim = -1; vector<ll> ans(n); vector<ll> left_lim(n); for(ll i = 0; i < n; i++){ if(cnt == c[j]) {ans[i] = ans[i-1] + 1, lim = (!v[i] ? i : lim), left_lim[i] = lim, cnt = 0, j++; continue;} if(v[i]) cnt++; else cnt = 0, lim = i; ans[i] = (i ? ans[i-1] : 0); left_lim[i] = lim; } return {ans, left_lim}; } pair<vector<ll>, vector<ll>> calc_r(ll n, ll k, vector<ll> &v, vector<ll> &c){ ll j = k-1, cnt = 0, lim = n; vector<ll> ans(n); vector<ll> right_lim(n); for(ll i = n-1; i >= 0; i--){ if(cnt == c[j]) {ans[i] = ans[i+1] + 1, lim = (!v[i] ? i : lim), right_lim[i] = lim, cnt = 0, j--; continue;} if(v[i]) cnt++; else cnt = 0, lim = i; ans[i] = (i < n-1 ? ans[i+1] : 0); right_lim[i] = lim; } return {ans, right_lim}; } string solve_puzzle(string s, vector<int> c) { ll n = s.size(), k = c.size(); vector<ll> v(n); for(ll i = 0; i < n; i++) { if(s[i] == '.') v[i] = 2; else if(s[i] == '_') v[i] = 0; else v[i] = 1; } auto[left_cnt, left_lim] = calc_l(n, k, v, c); auto[right_cnt, right_lim] = calc_r(n, k, v, c); for(ll i = 0; i < n; i++){ for(ll j = 0; j < k; j++){ dp[i][j] = (i+1 >= c[j] && (left_lim[i] < i - c[j] + 1) && s[i - c[j]] != 'X' && (j == 0 || pref[i - c[j] - 1][j])); cout << dp[i][j] << " "; pref[i+1][j+1] = pref[i][j] + dp[i][j]; } cout << "\n"; } string ans = s; for(ll i = 0; i < n; i++){ if(s[i] != '.') continue; bool white = (left_cnt[i] + right_cnt[i] >= k); bool black = 0; for(ll j = 0; j < k; j++) if(pref[i + c[j]][j+1] - (i > 0 ? pref[i-1][j+1]: 0)) black = 1; if(!white) ans[i] = 'X'; else if(!black) ans[i] = '_'; else ans[i] = '?'; } return ans; }

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
#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...