Submission #960260

#	Time	Username	Problem	Language	Result	Execution time	Memory
960260		irmuun	Paint By Numbers (IOI16_paint)	C++17	0 / 100	0 ms	344 KiB

paint

#include<bits/stdc++.h>
#include "paint.h"

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

vector<int>seg(vector<int>c,int l,int r){
    vector<int>d;
    for(int i=l;i<=r;i++){
        d.pb(c[i]);
    }
    return d;
}

int n,k;
bool check(string s,vector<int>c){
    bool ok=true;
    int cur=0;
    for(int i=0;i<s.size();){
        if(cur==c.size()||i+c[cur]-1>=s.size()) break;
        bool flag=true;
        for(int j=0;j<c[cur];j++){
            if(s[i+j]=='_'){
                flag=false;
                break;
            }
        }
        if(flag){
            i=i+c[cur]+1;
            cur++;
        }
        else{
            i++;
        }
    }
    if(cur==c.size()) return true;
    return false;
}

string solve_puzzle(string s,vector<int>c){
    n=s.size();
    k=c.size();
    vector<bool>can_white(n,0),must_white(n,0);
    for(int i=0;i<n;i++){
        if(s[i]=='_'){
            must_white[i]=true;
            continue;
        }
        if(s[i]=='.'){
            s[i]='_';
            if(check(s,c)==true){
                can_white[i]=true;
            }
            s[i]='.';
        }
    }
    vector<bool>can_black(n,0);
    for(int j=0;j<k;j++){
        for(int i=0;i<=n-c[j];i++){
            bool ok=true;
            for(int r=0;r<c[j];r++){
                if(s[i+r]=='_'){
                    ok=false;
                    break;
                }
            }
            if(ok){
                for(int r=0;r<c[j];r++){
                    s[i+r]='_';
                }
                char c1,c2;
                if(i>0){
                    c1=s[i-1];
                    s[i-1]='_';
                }
                if(i+c[i]<n){
                    c2=s[i+c[j]];
                    s[i+c[j]]='_';
                }
                if((j==0||check(s.substr(0,i),seg(c,0,j-1)))&&(j==k-1||check(s.substr(i+c[j],n-(i+c[j])),seg(c,j+1,k-1)))){
                    for(int r=0;r<c[j];r++){
                        can_black[i+r]=true;
                    }
                }
                if(i>0){
                    s[i-1]=c1;
                }
                if(i+c[j]<n){
                    s[i+c[j]]=c2;
                }
                for(int r=0;r<c[j];r++){
                    s[i+r]='.';
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        if(must_white[i]){
            s[i]='_';
        }
        else if(can_black[i]&&can_white[i]){
            s[i]='?';
        }
        else if(!can_black[i]){
            s[i]='_';
        }
        else{
            s[i]='X';
        }
    }
    return s;
}

Compilation message (stderr)

paint.cpp: In function 'bool check(std::string, std::vector<int>)':
paint.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i=0;i<s.size();){
      |                 ~^~~~~~~~~
paint.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if(cur==c.size()||i+c[cur]-1>=s.size()) break;
      |            ~~~^~~~~~~~~~
paint.cpp:26:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if(cur==c.size()||i+c[cur]-1>=s.size()) break;
      |                           ~~~~~~~~~~^~~~~~~~~~
paint.cpp:42:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     if(cur==c.size()) return true;
      |        ~~~^~~~~~~~~~
paint.cpp:23:10: warning: unused variable 'ok' [-Wunused-variable]
   23 |     bool ok=true;
      |          ^~
paint.cpp: In function 'std::string solve_puzzle(std::string, std::vector<int>)':
paint.cpp:95:30: warning: 'c2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   95 |                     s[i+c[j]]=c2;

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