Submission #482478

#	Time	Username	Problem	Language	Result	Execution time	Memory
482478		Lobo	Paint By Numbers (IOI16_paint)	C++17	100 / 100	612 ms	349940 KiB

paint

#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 200020

ii n, k, a[maxn], b[maxn], dp1[maxn][110][2], dp2[maxn][110][2];
ii ansb[maxn], answ[maxn], ps[maxn], qtdw[maxn];
string ans;
//0->.
//1->_
//2->X

std::string solve_puzzle(std::string s, std::vector<int> c) {
    //begin

    n = s.size();
    k = c.size();
    for(ii i = 1; i <= n; i++) {
        qtdw[i] = qtdw[i-1];
        if(s[i-1] == '.') a[i] = 0;
        else if(s[i-1] == '_') {
            qtdw[i]++;
            a[i] = 1;
        }
        else a[i] = 2;
    }
    for(ii i = 1; i <= k; i++) {
        b[i] = c[i-1];
    }

    for(ii i = 0; i <= n; i++) {
        for(ii j = 0; j <= k; j++) {
            for(ii ant = 0; ant <= 1; ant++) {
                if(i == 0 && j == 0) {
                    dp1[i][j][ant] = 1;
                    continue;
                }

                ii ans = 0;

                //if can be white:
                if(i != 0 && a[i] != 2) ans = max(ans, dp1[i-1][j][0]);

                //if can be black:
                if(j != 0 && ant == 0 && i-b[j]+1 >= 1 && qtdw[i] - qtdw[i-b[j]] == 0) ans = max(ans, dp1[i-b[j]][j-1][1]);

                dp1[i][j][ant] = ans;
            }
        }
    }


    for(ii i = n+1; i >= 1; i--) {
        for(ii j = k+1; j >= 1; j--) {
            for(ii ant = 0; ant <= 1; ant++) {
                if(i == n+1 && j == k+1) {
                    dp2[i][j][ant] = 1;
                    continue;
                }

                ii ans = 0;

                //if can be white:
                if(i != n+1 && a[i] != 2) ans = max(ans, dp2[i+1][j][0]);

                //if can be black:
                if(j != k+1 && ant == 0 && i+b[j]-1 <= n && qtdw[i+b[j]-1] - qtdw[i-1] == 0) ans = max(ans, dp2[i+b[j]][j+1][1]);

                dp2[i][j][ant] = ans;
            }
        }
    }


    for(ii i = 1; i <= n; i++) {
        for(ii j = 1; j <= k+1; j++) {
            //i is white
            if(a[i] != 2) answ[i] = max(answ[i], (dp1[i-1][j-1][0]&dp2[i+1][j][0]) );
        }

        for(ii j = 1; j <= k; j++) {
            //interval (i,i+b[j]-1) black

            if(i+b[j]-1 <= n && (dp1[i-1][j-1][1]&dp2[i+b[j]][j+1][1]) == 1 && qtdw[i+b[j]-1]-qtdw[i-1] == 0) {
                ps[i]++;
                ps[i+b[j]]--;
            }
        }

        ps[i]+= ps[i-1];
        if(ps[i] >= 1) ansb[i] = 1;

        if(answ[i] == 1 && ansb[i] == 1)
            ans+= '?';
        else if(answ[i] == 1)
            ans+= '_';
        else if(ansb[i] == 1) 
            ans+= 'X';
    }

    return ans;
}

• 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