제출 #792073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
792073		alvingogo	Paint By Numbers (IOI16_paint)	C++14	100 / 100	341 ms	84952 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

string solve_puzzle(string s, vector<int> c) {
    int n=s.size(),k=c.size();
    string ans=s;
    vector<int> nb(n),nw(n),pb(n),pw(n);
    int rb=n,rw=n;
    for(int i=n-1;i>=0;i--){
        if(s[i]=='X'){
            rb=i;
        }
        else if(s[i]=='_'){
            rw=i;
        }
        nb[i]=rb;
        nw[i]=rw;
    }
    int lb=-1,lw=-1;
    for(int i=0;i<n;i++){
        if(s[i]=='X'){
            lb=i;
        }
        else if(s[i]=='_'){
            lw=i;
        }
        pb[i]=lb;
        pw[i]=lw;
    }
    vector<vector<int> > dp(k);
    for(int i=0;i<k;i++){
        int rp=-1;
        for(int j=0;j+c[i]-1<n;j++){
            if(i==0){
                if((j==0 || pb[j-1]==-1) && nw[j]>=(j+c[i])){
                    dp[i].push_back(j);
                }
            }
            else{
                if(nw[j]<j+c[i]){
                    continue;
                }
                while(rp+1<dp[i-1].size() && dp[i-1][rp+1]<=j-1-c[i-1]){
                    rp++;
                }
                if(rp==-1){
                    continue;
                }
                if(dp[i-1][rp]+c[i-1]>(j==0?-1:pb[j-1])){
                    dp[i].push_back(j);
                }
            }
        }
    }
    
    for(int i=k-1;i>=0;i--){
        vector<int> z;
        if(i==k-1){
            for(auto h:dp[i]){
                if(h+c[i]<n && nb[h+c[i]]<n){

                }
                else{
                    z.push_back(h);
                }
            }
        }
        else{
            int rp=0;
            int xu=dp[i+1].size();
            for(auto h:dp[i]){
                while(rp<xu && dp[i+1][rp]<h+c[i]+1){
                    rp++;
                }
                if(rp==xu || dp[i+1][rp]>nb[h+c[i]]){
                }
                else{
                    z.push_back(h);
                }
            }
        }
        dp[i].swap(z);
    }
    vector<int> f(n);
    for(int j=0;j<k;j++){
        int rj=-1;
        for(int i=0;i<n;i++){
            while(rj+1<dp[j].size() && dp[j][rj+1]<=i){
                rj++;
            }
            if(rj!=-1 && dp[j][rj]>i-c[j]){
                f[i]|=1;
            }
        }
    }
    for(int i=0;i<*dp[0].rbegin();i++){
        f[i]|=2;
    }
    for(int j=1;j<k;j++){
        int ru=0,rs=-1;
        for(int i=0;i<n;i++){
            while(ru<dp[j].size() && dp[j][ru]<=i){
                ru++;
            }
            if(ru==dp[j].size()){
                continue;
            }
            while(rs+1<dp[j-1].size() && dp[j-1][rs+1]<=i-c[j-1]){
                rs++;
            }
            if(rs==-1){
                continue;
            }
            if(nb[dp[j-1][rs]+c[j-1]]>=dp[j][ru]){
                f[i]|=2;
            }
        }
    }
    for(int i=*dp[k-1].begin()+c[k-1];i<n;i++){
        f[i]|=2;
    }
    for(int i=0;i<n;i++){
        if(f[i]==1){
            ans[i]='X';
        }
        else if(f[i]==2){
            ans[i]='_';
        }
        else{
            ans[i]='?';
        }
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 while(rp+1<dp[i-1].size() && dp[i-1][rp+1]<=j-1-c[i-1]){
      |                       ~~~~^~~~~~~~~~~~~~~
paint.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             while(rj+1<dp[j].size() && dp[j][rj+1]<=i){
      |                   ~~~~^~~~~~~~~~~~~
paint.cpp:107:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |             while(ru<dp[j].size() && dp[j][ru]<=i){
      |                   ~~^~~~~~~~~~~~~
paint.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             if(ru==dp[j].size()){
      |                ~~^~~~~~~~~~~~~~
paint.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             while(rs+1<dp[j-1].size() && dp[j-1][rs+1]<=i-c[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