Submission #66120

#	Time	Username	Problem	Language	Result	Execution time	Memory
66120		MANcity	Paint By Numbers (IOI16_paint)	C++14	100 / 100	1933 ms	432000 KiB

paint

    #include<iostream>
    #include<cstdio>
    #include<fstream>
    #include<algorithm>
    #include<cmath>
    #include<map>
    #include<queue>
    #include<set>
    #include<stack>
    #include<string>
    #include<cstring>
    #include<vector>
    #include "paint.h"
    using namespace std;
    #define for1(i,n) for(int i=1;i<=(int)n;i++)
    #define for0(i,n) for(int i=0;i<=(int)n;i++)
    #define forn(i,n) for(int i=n;i>=1;i--)
    #define fo(i,x,y) for(int i=x;i<=(int)y;i++)
    #define fr(i,x,y) for(int i=x;i>=(int)y;i--)
    #define pb push_back
    #define mp make_pair
    #define LL long long
    const LL Mod=1000*1000*1000+7;
    int n,k;
    int dp[200002][102];
    int ap[200002][102];
    int minqan[200002];
    int minaj[200002];
    int mindzax[200002];
    int C[1002];
    string S;
    int xdir1(int i,int j)
    {
        if((i-C[j]+1)>minaj[i] && S[i-C[j]]!='X')
            return dp[max(0,i-C[j]-1)][j-1];
        else
            return 0;
    }
    int xdir2(int i,int j)
    {
        if((i-C[j]+1)>minaj[i] && S[i-C[j]]!='X')
            return ap[max(0,i-C[j]-1)][j-1];
        else
            return 0;
    }
    void CALC()
    {
        for1(i,n)
        {
            if(S[i-1]=='_')
                minaj[i]=i-1;
            else
                minaj[i]=minaj[i-1];
        }
    }
    void calc1()
    {
        CALC();
        dp[0][0]=1;
        for1(i,n)
            for0(j,k)
            {
                if(S[i]=='_')
                    dp[i][j]=dp[i-1][j];
                else
                {
                    if(S[i]=='X')
                        dp[i][j]=xdir1(i,j);
                    if(S[i]=='.')
                    {
                        dp[i][j]=max(dp[i-1][j],xdir1(i,j));
                    }
                }
            }
            return;
    }
    void calc2()
    {
        CALC();
        ap[0][0]=1;
        for1(i,n)
            for0(j,k)
            {
                if(S[i]=='_')
                    ap[i][j]=ap[i-1][j];
                else
                {
                    if(S[i]=='X')
                    {
                        ap[i][j]=xdir2(i,j);
                    }
                    if(S[i]=='.')
                    {
                        ap[i][j]=max(ap[i-1][j],xdir2(i,j));
                    }
                }
            }
            return;
    }
    int minusik[200002];
    int plusik[200002];
    int add[4*200002];
    void push(int v)
    {
        add[2*v]+=add[v];
        add[2*v+1]+=add[v];
        add[v]=0;
        return ;
    }
    void update(int left,int right,int l,int r,int v,int val)
    {
        if(l>r)
            return;
        if(add[v]>0)
            return;
        if(left==l && right==r)
        {
            add[v]+=val;
            return ;
        }
        else
        {
            int m=(left+right)/2;
            push(v);
            update(left,m,l,min(r,m),2*v,val);
            update(m+1,right,max(l,m+1),r,2*v+1,val);
        }
    }
    int get(int left,int right,int pos,int v)
    {
        if(add[v]>0)
            return 1;
        if(left==right)
        {
            if(add[v]>0)
            return 1;
            return 0;
        }
        else
        {
            int m=(left+right)/2;
            push(v);
            if(pos<=m)
                return get(left,m,pos,2*v);
            else
                return get(m+1,right,pos,2*v+1);
        }
    }
    string solve_puzzle(string s, vector<int> c)
    {
        k=c.size();
        n=s.size();
        for0(i,k-1)
            C[i+1]=c[i];
        S+='_';
        S+=s;
        calc1();
        S.clear();
        string t=s;
        reverse(s.begin(),s.end());
        S+='_';
        S+=s;
        for0(i,k-1)
            C[i+1]=c[k-1-i];
        calc2();
        S.clear();
        S+='_';
        S+=t;
        for0(i,k-1)
            C[i+1]=c[i];
        for1(i,n)
        {
            if(S[i]=='.')
            {
                int u=0;
                for0(j,k)
                {
                    u=max(u,(dp[i-1][j]+ap[n-i][k-j]));
                }
                if(u==2)
                    minusik[i]=1;
            }
        }
        CALC();
        vector<pair<int,int> > V;
        pair<int,int> used[200002];
        for1(j,k)
            for1(i,n)
            {
                if(S[i]!='_' && (i-C[j]+1)>minaj[i] && S[i-C[j]]!='X' && S[i+1]!='X')
                    if(dp[max(0,i-C[j]-1)][j-1]==1 && ap[max(n-i-1,0)][k-j]==1)
                    {
                        V.push_back(mp(i-C[j]+1,i));
                        used[i-C[j]+1].first=1;
                        used[i-C[j]+1].second=max(used[i-C[j]+1].second,i);
                    }
            }
        int a=1;
        while(1)
        {
            if(used[a].first==1)
            {
                int t=used[a].second;
                fo(j,a,t)
                {
                    plusik[j]=1;
                    if(used[j].first==1)
                        t=max(t,used[j].second);
                }
                a=t;
            }
            if(a==n)
                break;
            a++;
        }
        string ANSWER;
        for1(i,n)
        {
            if(S[i]!='.')
                ANSWER+=S[i];
            else
            {
                int u=0;
                if(plusik[i]==1 && minusik[i]==0)
                {
                    u=1;
                    ANSWER+='X';
                }
                if(plusik[i]==0 && minusik[i]==1)
                {
                    u=1;
                    ANSWER+='_';
                }
                if(plusik[i]==1 && minusik[i]==1)
                {
                    u=1;
                    ANSWER+='?';
                }
                if(u==0)
                    ANSWER+='X';
            }
        }
        return ANSWER;
    }

• 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