Submission #1078471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078471		Hugo1729	Paint By Numbers (IOI16_paint)	C++17	59 / 100	1 ms	448 KiB

paint

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

vector<int> greedy(string s, vector<int> c){
    int n = s.size();

    vector<int> ans(n,-1);

    int ptr=0;

    for(int i=0;i<n&&ptr<c.size();){
        int j=i;
        for(;j<i+c[ptr];j++){
            if(s[j]=='_')break;
        }

        // cout << j << '\n';

        if(j==i+c[ptr]){
            while(s[j]=='x')j++;

            for(int k=j-c[ptr];k<j;k++)ans[k]=ptr;
            // cout << j-c[ptr] << ' ' << j-1 << '\n';

            i=j+1;
            ptr++;
        }else{
            i=j+1;
        }
    }

    return ans;
}





string solve_puzzle(string s, vector<int> c) {
    vector<int> ans = greedy(s,c);

    int n = s.size();

    // for(int i : ans)cout << i << ' ';
    // cout << '\n';

    reverse(s.begin(),s.end());
    reverse(c.begin(),c.end());

    // cout << s  << '\n';
    // for(int i : ans)cout << i << ' ';

    // cout << '\n';

    vector<int> ans2 = greedy(s,c);

    reverse(ans2.begin(),ans2.end());
    reverse(s.begin(),s.end());
    reverse(c.begin(),c.end());

    int prev=-1,prev2=-1;

    string output="";

    for(int i=0;i<n;i++){
        if(ans2[i]!=-1)ans2[i]=c.size()-1-ans2[i];

        prev=max(ans[i],prev);
        prev2=max(ans2[i],prev2);

        if(s[i]!='.'){
            output+=s[i];
            continue;
        }

        if(ans[i]==ans2[i]&&prev==prev2){
            if(ans[i]==-1)output += "_";
            else output += "X";
        }else{
            output += "?";
        }

    }
    //cout << output;

    // cout << '\n';

    // for(int i : ans2)cout << i << ' ';

    // cout << '\n';





    return output;
}

Compilation message (stderr)

paint.cpp: In function 'std::vector<int> greedy(std::string, std::vector<int>)':
paint.cpp:12:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<n&&ptr<c.size();){
      |                      ~~~^~~~~~~~~

• 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