Submission #170284

#	Time	Username	Problem	Language	Result	Execution time	Memory
170284		arnold518	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1119 ms	59692 KiB

paint

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int MAXK = 100;

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

int cnt[MAXN+10];
bool dp[MAXN+10][MAXK+10], vis[MAXN+10][MAXK+10];
int black[MAXN+10], white[MAXN+10];

bool solve(int n, int k)
{
    int i, j;

    if(n>N && k>K) return true;
    if(n>N) return false;

    bool &ret=dp[n][k];
    if(vis[n][k]) return ret;
    ret=false; vis[n][k]=true;

    if(S[n]!='X' && solve(n+1, k))
    {
        ret=true;
        white[n]++;
        white[n+1]--;
        //printf("PASS %d %d\n", n, k);
    }

    if(n+C[k]<=N+1 && k<=K)
    {
        if(cnt[n+C[k]-1]-cnt[n-1]==0 && S[n+C[k]]!='X' && solve(n+C[k]+1, k+1))
        {
            ret=true;
            black[n]++;
            black[n+C[k]]--;
            white[n+C[k]]++;
            white[n+C[k]+1]--;
            //printf("FILL %d %d\n", n, k);
        }
    }

    //printf("%d %d : %d\n", n, k, ret);
    return ret;
}

string solve_puzzle(string _S, vector<int> _C)
{
    int i, j;
    S=_S; C=_C;
    N=S.size(); K=C.size();

    S="@"+S+"@";
    C.insert(C.begin(), -1);

    for(i=1; i<=N; i++) cnt[i]=cnt[i-1]+(S[i]=='_');

    solve(1, 1);

    for(i=1; i<=N; i++) black[i]+=black[i-1];
    for(i=1; i<=N; i++) white[i]+=white[i-1];

    ans.resize(N);

    for(i=1; i<=N; i++)
    {
        if(black[i] && white[i]) ans[i-1]='?';
        else if(black[i]) ans[i-1]='X';
        else if(white[i]) ans[i-1]='_';
    }

    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool solve(int, int)':
paint.cpp:22:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
paint.cpp:22:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
paint.cpp: In function 'std::__cxx11::string solve_puzzle(std::__cxx11::string, std::vector<int>)':
paint.cpp:58:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

• 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