Submission #1089020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089020		Tymond	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	2396 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int MAXN = 2e5 + 7;
int sum1[MAXN];
int mxPref[MAXN];
int mxSuf[MAXN];
int pref0[MAXN];
int n, m;
string s;
vi c;

string solve_puzzle(string xd, vi lol){
    s = xd;
    c = lol;
    n = sz(s);
    m = sz(c);

    int wsk = m - 1;
    int akt = 0;
    mxSuf[n + 1] = m;
    mxPref[0] = -1;
    int ost = 0;
    int flag = 0;
    for(int i = n; i >= 1; i--){       
        if(s[i - 1] == '_'){
            if(flag){
                int pocz = i;
                while(s[pocz] != 'X'){
                    pocz++;
                }

                for(int j = pocz + 1; j <= ost; j++){
                    mxSuf[j]++;
                }

                ost = 0;
            }
            
            flag = 0;
            pref0[i]++;
            akt = 0;
            mxSuf[i] = wsk+1;
            continue;
        }
        if(wsk == -1){
            mxSuf[i] = 0;
            continue;
        }

        akt++;
        if(s[i - 1] == 'X'){
            flag = 1;
            if(akt == 0){
                mxSuf[i + 1]++;
                flag = 0;
                akt = -1;
            }
        }
        if(akt == c[wsk]){
            wsk--;
            akt = -1;
            flag = 0;
            ost = i;
            mxSuf[i] = wsk + 1;
        }else{
            if(flag){
                mxSuf[i] = m + 1;
            }else{
                mxSuf[i] = wsk + 1;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        pref0[i] += pref0[i - 1];
    }

    wsk = 0;
    akt = 0;
    flag = 0;
    for(int i = 1; i <= n; i++){
        if(s[i - 1] == '_'){
            if(flag){
                int pocz = i - 2;
                while(s[pocz] != 'X'){
                    pocz--;
                }

                for(int j = pocz - 1; j >= ost; j--){
                    mxPref[j]--;
                }

                ost = 0;
            }

            flag = 0;
            akt = 0;
            mxPref[i] = wsk - 1;
            continue;
        }
        if(wsk == m){
            mxPref[i] = wsk - 1;
            continue;
        }
        akt++;
        if(s[i - 1] == 'X'){
            flag = 1;
            if(akt == 0){
                mxPref[i - 1]--;
                flag = 0;
                akt = -1;
            }
        }
        if(akt == c[wsk]){
            wsk++;
            akt = -1;
            flag = 0;
            ost = i;
            mxPref[i] = wsk - 1;
        }else{
            if(flag){
                mxPref[i] = -2;
            }else{
                mxPref[i] = wsk - 1;
            }
        }
    }

    for(int i = 0; i < m; i++){
        for(int j = 1; j <= n; j++){
            if((j == 1 ? (i == 0) : (mxPref[j - 2] >= i - 1)) && j + c[i] <= n + 1 && (j + c[i] >= n ? (i == m - 1) : (mxSuf[j + c[i] + 1] <= i + 1)) && pref0[j + c[i] - 1] - pref0[j - 1] == 0){
                if(j > 1){
                    if(s[j - 2] == 'X'){
                        continue;
                    }
                }
                if(j < n){
                    if(s[j] == 'X'){
                        continue;
                    }
                }
                sum1[j]++;
                sum1[j + c[i]]--;
            }
        }
    }

    /*for(int i = 1; i <= n; i++){
        cout << mxPref[i] << ' ' << mxSuf[i] << '\n';
    }*/

    string res = "";
    int sum = 0;
    for(int i = 1; i <= n; i++){
        sum += sum1[i];
        if(s[i - 1] != '.'){
            res += s[i - 1];
            continue;
        }

        bool f = 0;
        if(mxSuf[i + 1] == 0){
            f = 1;
        }
        for(int j = 0; j < m; j++){
            if(mxPref[i - 1] >= j && mxSuf[i + 1] <= j + 1){
                f = 1;
            }
        }

        if(f){
            if(sum > 0){
                res += "?";
            }else{
                res += "_";
            }
        }else{
            res += "X";
        }
    }
    return res;
}

/*int main(){
    cout << solve_puzzle("....X.", {3, 1}) << '\n';
    return 0;
}*/

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 27 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10