Submission #794626

#	Time	Username	Problem	Language	Result	Execution time	Memory
794626		I_Love_EliskaM_	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1100 ms	343376 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
const int inf=1e9+9;

const int N=2e5+55;
const int K=105;

int dp[N][K];
int dp2[N][K];
int can[N];
int cant[N];

void yes(int l, int r) {
    can[l]++;
    can[r+1]--;
}

int query(vector<int>&a, int l, int r) {
    if (l>r) return 0;
    return a[r+1]-a[l];
}

string solve_puzzle(string s, vector<int> c) {
    s+='_';
    int n=s.size();
    int k=c.size();

    forn(i,n) cant[i]=0;

    vector<int> X(n+1), _(n+1);
    forn(i,n) X[i+1]=X[i]+(s[i]=='X');
    forn(i,n) _[i+1]=_[i]+(s[i]=='_');

    vector<vector<int>> pos(k+1);
    vector<int> it(k+1);

    pos[0].pb(0);
    dp[0][0]=1;

    for(int i=1; i<=n; ++i) {
        forn(j,k) {
            int x=c[j]+1;

            if (i-x<0) continue;
            if (!pos[j].size()) continue;
            if (pos[j][0]>i-x) continue;
            
            int last;        
            while (it[j]<pos[j].size() && pos[j][it[j]]<=i-x) ++it[j];
            --it[j];
            last=pos[j][it[j]];

            int y=1, z=1;

            y&=query(_,i-x,i-2)==0;
            y&=s[i-1]!='X';

            z&=query(X,last,i-x-1)==0;

            dp[i][j+1]=y&z;
            if (dp[i][j+1]) pos[j+1].pb(i);
        }
    }

    vector<vector<int>> pos2(k+2);
    vector<int> it2(k+2);
    pos2[k+1].pb(n+1);
    dp2[n+1][k+1]=1;
    for (int i=n; i>0; --i) {
        for(int j=k; j>0; --j) {
            int x=c[j-1]+1;

            if (i+x>n+1) continue;
            if (!dp[i+x-1][j]) continue;
            if (!pos2[j+1].size()) continue;
            if (pos2[j+1][0]<i+x) continue;

            int last;
            for(auto&v:pos2[j+1]) if (v>=i+x) last=v;
            while (it2[j+1]<pos2[j+1].size() && pos2[j+1][it2[j+1]]>=i+x) ++it2[j+1];
            --it2[j+1];
            last=pos2[j+1][it2[j+1]];

            int y=1, z=1;

            y&=query(_,i-1,i+x-3)==0;
            y&=s[i+x-2]!='X';

            z&=query(X,i+x-2,last-2)==0;
            dp2[i][j]=y&z;

            if (dp2[i][j]) pos2[j].pb(i);

        }   
    }
    it.assign(k+1,0);
    it2.assign(k+2,0);
    for (int i=1; i<=n; ++i) {
        forn(j,k+1) {
            if (pos[j][0]>i) continue;
            if (pos2[j+1][0]<=i) continue;

            int l,r;

            while (it[j]<pos[j].size() && pos[j][it[j]]<=i) ++it[j];
            --it[j];
            l=pos[j][it[j]];

            while (it2[j+1]<pos2[j+1].size() && pos2[j+1][it2[j+1]]>i) ++it2[j+1];
            --it2[j+1];
            r=pos2[j+1][it2[j+1]];

            int z=1;
            z&=query(X,l,r-2)==0;

            if (z) cant[i-1]=1;
            //cout<<"? "<<i<<' '<<j<<' '<<l<<' '<<r<<"  "<<z<<'\n';
        }
    }
    
    for (int i=0; i<=n+1; ++i) dp[i][0]=dp2[i][k+1]=1;

    it2.assign(k+2,0);
    for (int i=1; i<=n; ++i) {
        for(int j=1; j<=k; ++j) {
            int x=c[j-1]+1;
            if (dp[i][j]) {
                if (!dp2[i-x+1][j]) continue;
                if (pos2[j+1][0]<=i) continue;

                int last;
                while (it2[j+1]<pos2[j+1].size() && pos2[j+1][it2[j+1]]>i) ++it2[j+1];
                --it2[j+1];
                last=pos2[j+1][it2[j+1]];

                if (dp2[last][j+1]) {
                    yes(i-x,i-2);
                }
            }
        }
    }
    
    string ans(n,'?');
    int sum=0;
    forn(i,n) {
        sum+=can[i];
        if (sum) {
            if (cant[i]) continue;
            ans[i]='X';
        } else {
            ans[i]='_';
        }
    }
    forn(i,n) {
        if (s[i]=='X') {
            assert(ans[i]!='_');
            ans[i]='X';
        }
    }
    ans.pop_back();

    return ans;

}

Compilation message (stderr)

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:56:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             while (it[j]<pos[j].size() && pos[j][it[j]]<=i-x) ++it[j];
paint.cpp:87:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             while (it2[j+1]<pos2[j+1].size() && pos2[j+1][it2[j+1]]>=i+x) ++it2[j+1];
paint.cpp:112:25: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             while (it[j]<pos[j].size() && pos[j][it[j]]<=i) ++it[j];
paint.cpp:116:28: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |             while (it2[j+1]<pos2[j+1].size() && pos2[j+1][it2[j+1]]>i) ++it2[j+1];
paint.cpp:139:32: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                 while (it2[j+1]<pos2[j+1].size() && pos2[j+1][it2[j+1]]>i) ++it2[j+1];

• 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