제출 #65980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
65980		MANcity	Paint By Numbers (IOI16_paint)	C++14	90 / 100	234 ms	147716 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[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(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(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;
    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));
                }
        }
    for0(i,V.size()-1)
        fo(j,V[i].first,V[i].second)
            update(1,n,V[i].first,V[i].second,1,1);
    for1(i,n)
        if(get(1,n,i,1)==1)
            plusik[i]=1;
    string ANSWER;
    for1(i,n)
    {
        if(S[i]!='.')
            ANSWER+=S[i];
        else
        {
            if(plusik[i]==1 && minusik[i]==0)
                ANSWER+='X';
            if(plusik[i]==0 && minusik[i]==1)
                ANSWER+='_';
            if(plusik[i]==1 && minusik[i]==1)
                ANSWER+='?';
            if(plusik[i]==0 && minusik[i]==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: 0 / 10