Submission #1210227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210227		sano	Paint By Numbers (IOI16_paint)	C++20	100 / 100	913 ms	270932 KiB

paint

#include "paint.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<int, int>
#define pld pair<ld, ld>
#define NEK 2000000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

string solve_puzzle(string s, vec<int> c) {
    int n = s.size();
    vec<bitset<101>> v(n+5);
    v[0][0] = 1;
    vec<pii> b;
    s.push_back('_');
    vec<bool> mw(n+100);
    int k = c.size();
    vec<bitset<101>> dp(n + 1);
    dp[n][c.size()] = 1;
    vec<int> ps(n + 1, 0);
    ps[0] = 0;
    For(i, n) {
        if (s[i] == '_') ps[i+1]++;
        ps[i+1] += ps[i];
    }
    rfor(i, n - 1) {
        For(j, k+1) {
            //ostanem bielym
            if(s[i] != 'X') dp[i][j] = dp[i + 1][j];
            //ostanem ciernym
            if (j == k) continue;
            if (i + c[j] > n) continue;
            int poc_b = ps[i + c[j]] - ps[i];
            if (poc_b != 0) continue;
            if (s[i + c[j]] == 'X') continue;
            if (i + c[j] == n) {
                dp[i][j] = dp[i][j] | dp[n][j + 1];
                continue;
            }
            if(s[i] != '_') dp[i][j] = dp[i][j] || dp[i + c[j] + 1][j + 1];
        }
    }
    For(i, n) {
        for (int j = 0; j <= k; j++) {
            if (!v[i][j]) continue;
            //idem cez vsetky moznosti toho co vybavili predomnou
            //skus sa dat ako biely
            if (s[i] != 'X') {
                if (dp[i + 1][j]) {
                    mw[i] = 1;
                    v[i + 1][j] = 1;
                }
            }
            //skus sa dat ako cierny
            if (s[i] != '_' && j != k) {
                int chod = i + c[j] + 1;
                if (chod == n + 1) chod = n;
                if (i + c[j] <= n && (ps[i + c[j]] - ps[i]) == 0 && s[i + c[j]] != 'X' && dp[chod][j + 1]) {
                    b.push_back({ i, i + c[j] - 1 });
                    mw[i + c[j]] = 1;
                    v[i + c[j] + 1][j + 1] = 1;
                }
            }
        }
    }
    sort(all(b));
    vec<bool> mb(n, 0);
    int som = 0;
    int kon = -1;
    For(i, n){
        while (som < b.size() && b[som].ff <= i) {
            kon = max(kon, b[som].ss);
            som++;
        }
        if (i <= kon) mb[i] = 1;
    }
    For(i, n) {
        if (!mw[i]) {
            s[i] = 'X';
            continue;
        }
        if (!mb[i]) {
            s[i] = '_';
            continue;
        }
        s[i] = '?';
    }
    s.pop_back();
    return s;
}


/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    int k; cin >> k;
    vec<int> c(k);
    For(i, k) cin >> c[i];
    cout << solve_puzzle(s, c) << '\n';
    return 0;
}*/

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
      |         ^~~~

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