Submission #1205957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205957		loiiii12358	Paint By Numbers (IOI16_paint)	C++20	59 / 100	0 ms	328 KiB

paint

#include "paint.h"

#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;

std::string solve_puzzle(std::string s, std::vector<int> c) {
    string ans=s;
    int cnt=0,pt=0;
    vector<int> tmp,l(c.size()),r(c.size());
    stack<int> s1,s2;
    vector<pair<vector<int>,pair<int,int>>> inter;
    for(int i=0;i<s.size();i++){
        if(s[i]=='X'){
            tmp.push_back(i);
        }else if(s[i]=='_'){
            if(cnt<=i-1){
                inter.push_back({tmp,{cnt,i-1}});
            }
            cnt=i+1;
        }
    }
    inter.push_back({tmp,{cnt,s.size()-1}});
    for(int i=c.size()-1;i>=0;i--){
        s2.push(c[i]);
    }
    for(int i=0;i<inter.size();i++){
        if(inter[i].first.size()==0){
            cnt=inter[i].second.first;
            while(!s2.empty()&&cnt+s2.top()-1<=inter[i].second.second){
                l[s1.size()]=cnt;
                cnt+=s2.top()+1;
                s1.push(s2.top());
                s2.pop();
            }
        }
    }
    for(int i=inter.size()-1;i>=0;i--){
        if(inter[i].first.size()==0){
            cnt=inter[i].second.second;
            while(!s1.empty()&&cnt-s1.top()+1>=inter[i].second.first){
                r[s1.size()-1]=cnt;
                cnt-=s1.top()+1;
                s2.push(s1.top());
                s1.pop();
            }
        }
    }
    // cout << c.size() << '\n';
    // for(int i=0;i<c.size();i++){
    //     cout << l[i] << ' ' << r[i] << '\n';
    // }
    tmp.clear();
    tmp.resize(s.size(),0);
    for(int i=0;i<c.size();i++){
        cnt=0;
        for(int j=0;j<inter.size();j++){
            if(inter[j].second.second<l[i]){
                continue;
            }else if(inter[j].second.first>r[i]){
                break;
            }else if(inter[j].second.second-inter[j].second.first+1<c[i]){
                continue;
            }
            cnt++;
            pt=j;
            for(int k=max(inter[j].second.first,l[i]);k<=min(inter[j].second.second,r[i]);k++){
                tmp[k]++;
            }
        }
        if(cnt==1){
            for(int k=min(inter[pt].second.second,r[i])-c[i]+1;k<max(inter[pt].second.first,l[i])+c[i];k++){
                ans[k]='X';
            }
        }
    }
    for(int i=0;i<s.size();i++){
        if(ans[i]=='.'){
            if(tmp[i]==0){
                ans[i]='_';
            }else{
                ans[i]='?';
            }
        }
    }
    return ans;
}

Compilation message (stderr)

paint.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
paint_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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