Submission #431926

#	Time	Username	Problem	Language	Result	Execution time	Memory
431926		davi_bart	Paint By Numbers (IOI16_paint)	C++17	90 / 100	2065 ms	61740 KiB

paint

#include "paint.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ld long double
#define pb push_back
bool memo[200010][101][2];
bool vis[200010][101];
int N,K;
string x;
vector<int> v;
bool check(int a,int b){
    if(b>N)return 0;
    for(int i=a;i<b;i++)if(x[i]=='_')return 0;
    if(b<N && x[b]=='X')return 0;
    return 1;
}
bool ok(int pos,int c){
    if(pos>=N && c==v.size())return 1;
    if(pos>=N)return 0;
    if(vis[pos][c])return memo[pos][c][0]|memo[pos][c][1];
    vis[pos][c]=1;

    if(x[pos]=='_')return memo[pos][c][0]=ok(pos+1,c);
    if(x[pos]=='X'){
        if(c==v.size() || !check(pos,pos+v[c]))return memo[pos][c][1]=0;
        memo[pos][c][1]=ok(pos+v[c]+1,c+1);
        if(memo[pos][c][1])memo[pos+v[c]][c][0]=1;
        return memo[pos][c][1];
    }


    memo[pos][c][0]=ok(pos+1,c);
    if(c!=v.size() && check(pos,pos+v[c])){
        memo[pos][c][1]=ok(pos+v[c]+1,c+1);
        if(memo[pos][c][1])memo[pos+v[c]][c][0]=1;
    }else memo[pos][c][1]=0;

    return memo[pos][c][0]|memo[pos][c][1];
}
string solve_puzzle(string s,vector<int> c){

    N=s.size();K=c.size();
    x=s;
    v=c;
    ok(0,0);
    string ans=s;
    vector<int> ma(N,0);
    for(int i=0;i<N;i++){
        for(int j=0;j<K;j++){
            //ok(i,j);
            if(memo[i][j][1])ma[i]=max(ma[i],c[j]);
        }
    }
    for(int i=N-1;i>=0;i--){
        for(int j=i;j<i+ma[i];j++)memo[j][0][1]=1;
    }
    for(int i=0;i<N;i++){
        bool zero=0,uno=0;
        for(int j=0;j<=K;j++)zero|=memo[i][j][0];
        for(int j=0;j<=K;j++)uno|=memo[i][j][1];

        if(zero && uno)ans[i]='?';
        else if(zero)ans[i]='_';
        else if(uno)ans[i]='X';
        else ans[i]='O';
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'bool ok(int, int)':
paint.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if(pos>=N && c==v.size())return 1;
      |                  ~^~~~~~~~~~
paint.cpp:29:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if(c==v.size() || !check(pos,pos+v[c]))return memo[pos][c][1]=0;
      |            ~^~~~~~~~~~
paint.cpp:37:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(c!=v.size() && check(pos,pos+v[c])){
      |        ~^~~~~~~~~~

• 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: 0 / 10