Submission #617227

#	Time	Username	Problem	Language	Result	Execution time	Memory
617227		A_D	Paint By Numbers (IOI16_paint)	C++14	32 / 100	1 ms	308 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;
const int N=2e5+100;
int pre[N];
int suf[N];

string solve_puzzle(string s,vector<int> c){

    string ans=s;

    int n=s.size();
    int k=c.size();
    int sum=1;
    pre[0]=0;
    for(int i=1;i<n;i++){
        if(pre[i-1]==k){
            pre[i]=k;
            continue;
        }
        if(sum==c[pre[i-1]]){
            pre[i]=pre[i-1]+1;
            i++;
            if(i==n)break;
            pre[i]=pre[i-1];
            sum=1;
        }
        else{
            pre[i]=pre[i-1];
            sum++;
        }
    }
    sum=1;
    suf[n-1]=k-1;

    for(int i=n-2;i>=0;i--){
        if(suf[i+1]==-1){
            suf[i]=-1;
            continue;
        }
        if(sum==c[suf[i+1]]){
            suf[i]=suf[i+1]-1;
            i--;
            if(i==-1)break;
            suf[i]=suf[i+1];
            sum=1;
        }
        else{
            suf[i]=suf[i+1];
            sum++;
        }
    }
    if(suf[0]==-1){
        ans[0]='?';
    }
    else{
        ans[0]='X';
    }
    if(pre[n-1]==k){
        ans[n-1]='?';
    }
    else{
        ans[n-1]='X';
    }
    for(int i=1;i<n-1;i++){
        if(pre[i]==suf[i]){
            ans[i]='X';
            if((pre[i]!=pre[i-1])&&(suf[i]!=suf[i+1])){

            }
        }
        else{
            if((pre[i]==suf[i]+1)&&(pre[i]!=pre[i-1])&&(suf[i]!=suf[i+1])){
                ans[i]='_';

            }
            else ans[i]='?';
        }
    }

//    for(int i=0;i<n;i++)cout<<pre[i]<<" ";cout<<"\n";
  //  for(int i=0;i<n;i++)cout<<suf[i]<<" ";cout<<"\n";


    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 3 / 3
• Subtask 3: 22 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10