Submission #431945

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

paint

#include "paint.h"
#pragma GCC optimize("O3","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx")
#include <x86intrin.h>
#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;
bitset<201000> k;
bool check(int a,int b){
    if(b>N)return 0;
    if(x[a]=='_')return 0;
    int o=k._Find_next(a);
    if(o<b)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;
    for(int i=0;i<N;i++)k[i]=s[i]=='_';
    k[200009]=1;
    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=0;i<N;i++){
        int fine=i+ma[i];
        for(int j=i;j<fine;j++){
            memo[j][0][1]=1;
            fine=max(fine,j+ma[j]);
        }
        if(fine>i)i=fine-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];
            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:3: warning: ignoring '#pragma GCC option' [-Wunknown-pragmas]
    3 | #pragma GCC option("arch=native","tune=native","no-zero-upper")
      | 
paint.cpp: In function 'bool ok(int, int)':
paint.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     if(pos>=N && c==v.size())return 1;
      |                  ~^~~~~~~~~~
paint.cpp:35:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         if(c==v.size() || !check(pos,pos+v[c]))return memo[pos][c][1]=0;
      |            ~^~~~~~~~~~
paint.cpp:43:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     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