Submission #1089503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089503		Tymond	Paint By Numbers (IOI16_paint)	C++17	0 / 100	0 ms	348 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;
const int MAXK = 107;
int Sum[MAXN];
int pref[MAXN][MAXK];
int suf[MAXN][MAXK];
int pre[MAXN];
int nxt[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 x = -1;
    for(int i = 0; i < n; i++){
        if(s[i] != '_'){
            pre[i] = x;
        }else{
            pre[i] = i;
            x = i;
        }
    }
    x = n;
    for(int i = n - 1; i >= 0; i--){
        if(s[i] != '_'){
            nxt[i] = x;
        }else{
            nxt[i] = i;
            x = i;
        }
    }

    pref[0][0] = 1;
    for(int i = 0; i < n - 1; i++){
        if(s[i] != 'X'){
            for(int j = 0; j <= m; j++){
                pref[i + 1][j] = pref[i][j];
            }
        }

        if(s[i] != '_'){
            for(int j = 0; j < m; j++){
                if(pre[i] < i - c[j] + 1 && i - c[j] + 1 >= 0){
                    if(i - c[j] + 1 == 0){
                        if(j == 0){
                            pref[i + 1][j + 1] = 1;
                        }
                        continue;
                    }
                    if(s[i - c[j]] != 'X' && pref[i - c[j]][j]){
                        pref[i + 1][j + 1] = 1;
                    }
                }
            }
        }
    }

    suf[n - 1][m] = 1;
    suf[n][m] = 1;
    for(int i = n - 1; i > 0; i--){
        if(s[i] != 'X'){
            for(int j = 0; j <= m; j++){
                suf[i - 1][j] = suf[i][j];
            }
        }

        if(s[i] != '_'){
            for(int j = 1; j <= m; j++){
                if(nxt[i] > i + c[j - 1] - 1 && i + c[j - 1] - 1 < n){
                    if(i + c[j - 1] - 1 == n - 1){
                        if(j == m){
                            suf[i - 1][j - 1] = 1;
                        }
                        continue;
                    }
                    if(s[i + c[j - 1]] != 'X' && suf[i + c[j - 1]][j]){
                        suf[i - 1][j - 1] = 1;
                    }
                }
            }
        }
    }

    /*for(int i = 0; i < n; i++){
        for(int j = 0; j <= m; j++){
            cout << pref[i][j] << ' ';
        }
        cout << '\n';
    }*/

    for(int i = 0; i < n; i++){
        //sprawdź czy istnieją takie rozwiązania w których masz _
        if(s[i] != '.'){
            continue;
        }

        bool f = 0;
        for(int j = 0; j <= m; j++){
            if(pref[i][j] && suf[i][j]){
                f = 1;
            }
        }


        if(!f){
            s[i] = 'X';
        }
    }

    //cout << s << '\n';

    for(int j = 0; j < m; j++){
        for(int i = 0; i + c[j] - 1 < n; i++){
            if(nxt[i] > i + c[j] - 1){
                bool ok = 1;
                if(i == 0){
                    if(j != 0){
                        ok = 0;
                    }
                }else{
                    if(!pref[i - 1][j]){
                        ok = 0;
                    }

                    if(s[i - 1] == 'X'){
                        ok = 0;
                    }
                }

                if(i + c[j] < n){
                    if(!suf[i + c[j]][j + 2]){
                        ok = 0;
                    }
                    if(s[i + c[j]] == 'X'){
                        ok = 0;
                    }
                }else{
                    if(j != m - 1){
                        ok = 0;
                    }
                }

                if(ok){
                    Sum[i]++;
                    Sum[i + c[j]]--;
                }
            }
        }
    }
 
    string res = "";
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += Sum[i];
        if(s[i] != '.'){
            res += s[i];
            continue;
        }
 
        if(sum > 0){
            res += "?";
        }else{
            res += "_";
        }
    }
    return res;
}
 
/*int main(){
    cout << solve_puzzle("........", {3, 4}) << '\n';
    return 0;
}*/

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