Submission #836492

#	Time	Username	Problem	Language	Result	Execution time	Memory
836492		Ellinor	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1202 ms	104412 KiB

paint

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
#include <cstdlib>
#include <set>
#include <iomanip>
#include <limits>
#include <map>
#include <assert.h>
#include <algorithm>
#include <list>
#include <iterator>
#include <fstream>
#include <random>
#include <unordered_map>
#include <array>
//#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for (int i = (a); i < b; i++)
#define rrep(i,a) for (int i = (a) - 1; i >= 0; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<bool, bool> pbb;

// fast

#include "paint.h" // !

#include <cstdlib>

//
vector<vector<int>> dp; // dp
vector<pbb> alts;
//vector<bool> white_alts, black_alts;

int N, K;
string S;
vector<int> C;

vector<int> white_inds;

vector<int> black_start;


// ?
bool go(int nat, int kat)
{
    //if (kat >= K) return true;
    if (nat >= N && kat >= K) return true;
    if (nat >= N) return false;

    if (dp[nat][kat] != -1) return bool(dp[nat][kat]); // ??

    if (S[nat] == '_')
    {
        dp[nat][kat] = go(nat + 1, kat);
    }

    else if (S[nat] == 'X')
    {
        if (kat >= K)
        {
            dp[nat][kat] = false;
        }

        else
        {
            // when next white, nw_ind - nat >= C[kat] -> yay
            int wi;
            if (white_inds.size() == 0) wi = N;
            else if (nat > white_inds[white_inds.size() - 1]) wi = N;
            else
            {
                int wii = lower_bound(all(white_inds), nat) - white_inds.begin();
                wi = white_inds[wii];
            }

            if (wi - nat >= C[kat] && S[nat + C[kat]] != 'X')
            {
                dp[nat][kat] = go(nat + C[kat] + 1, kat + 1); // +1 !!
                if (dp[nat][kat]) {
                    alts[nat + C[kat]].second = true;
                    black_start[nat] = max(black_start[nat], C[kat]);
                }
            }
            else
            {
                dp[nat][kat] = false;
            }
        }
    }

    else if (S[nat] == '.') //
    {
        if (kat >= K)
        {
            bool b = false, w;

            w = go(nat + 1, kat);

            if (w)
            {
                alts[nat].second = true;
            }

            dp[nat][kat] = w;
        }

        else
        {
            bool b, w;
            // black ?
            int wi;
            if (white_inds.size() == 0) wi = N;
            else if (nat > white_inds[white_inds.size() - 1]) wi = N;
            else 
            {
                int wii = lower_bound(all(white_inds), nat) - white_inds.begin();
                wi = white_inds[wii];
            }

            if (wi - nat >= C[kat] && S[nat + C[kat]] != 'X')
            {
                b = go(nat + C[kat] + 1, kat + 1); // +1
                if (b) {
                    alts[nat + C[kat]].second = true;
                    black_start[nat] = max(black_start[nat], C[kat]);
                }
            }
            else b = false;

            w = go(nat + 1, kat);

            //assert(b || w);

            if (b || w)
            {
                if (b) alts[nat].first = true;
                if (w) alts[nat].second = true;
            }

            dp[nat][kat] = (b || w);
        }
    }

    return bool(dp[nat][kat]);
}


std::string solve_puzzle(std::string s, std::vector<int> c) 
{
    N = s.size();
    K = c.size();
    S = s;
    C = c;

    dp.assign(N, vector<int>(K + 1, -1));
    alts.assign(N, make_pair(false, false));

    black_start.assign(N, -1);

    rep(i,0,N) {
        if (S[i] == '_') white_inds.pb(i);
    }

    go(0,0); //

    int reach = -1; // inc
    rep(i,0,N)
    {
        if (black_start[i] != -1) reach = max(reach, i + black_start[i] - 1);
        if (i <= reach) alts[i].first = true;
    }

    string ret = "";

    rep(i,0,N) {
        if (S[i] == '_') ret += '_';
        else if (S[i] == 'X') ret += 'X';
        else if (alts[i].first && alts[i].second) ret += '?';
        else if (alts[i].first) ret += 'X';
        else if (alts[i].second) ret += '_';
        else {
            ret += 'X';
        }
    }

    return ret;
}

Compilation message (stderr)

paint.cpp: In function 'bool go(int, int)':
paint.cpp:102:18: warning: unused variable 'b' [-Wunused-variable]
  102 |             bool b = false, w;
      |                  ^

• 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