Submission #592453

#	Time	Username	Problem	Language	Result	Execution time	Memory
592453		wdjpng	Paint By Numbers (IOI16_paint)	C++17	7 / 100	1 ms	308 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()

using namespace std;

int n,k;
vector<int> solve(string s, vector<signed>c)
{
    vector<int>res(n);

    vector<int>pref(n,0);
    rep(i,n) pref[i]=s[i]=='_';
    rep(i,n-1) pref[i+1]+=pref[i];

    int curc = 0, lasttakeni=-2;
    for(int i = 0; i < n; i++)
    {
        if(curc!=c.size()&&i+1-c[curc]>lasttakeni+1&&pref[i]-((i-c[curc]<0)?0:pref[i-c[curc]])==0)
        {
            lasttakeni=i;
            curc++;
        }
        res[i]=curc-1;
    }
    return res;
}
string solve_puzzle(string s, vector<signed> c) {
    n = s.size(), k = c.size();

    vector<int>l=solve(s,c);
    l.push_back(k-1);

    vector<signed>revc = c; string revs=s;
    reverse(all(revc)); reverse(all(revs));

    vector<int>r=solve(revs, revc);
    rep(i,n) r[i]=k-1-r[i];
    reverse(all(r));
    r.push_back(k);

    string res=s;
    rep(i,n)
    {
        if(s[i]!='.') continue;
        bool _pos = !(((i==0)?0:(l[i-1]+1))<r[i+1]), xpos=true;

        if(i==0||s[i-1]=='_')
        {
            int next_ = find(s.begin()+i,s.end(),'_')-s.begin();
            int sum = -1;
            for(int j = l[i]+1; j < r[next_]; j++) sum+=c[j]+1;
            if(sum==next_-i)
            {
                int k = i;
                for(int j = l[i]+1; j < r[next_]; j++)
                {
                    rep(r,c[j]) res[k++]='X';
                    if(j<l[next_]) res[k++]='_';
                }
                i=k;
                continue;
            } 
            int minn=1e9;
            for(int j = r[i]; j <= l[next_]; j++) minn=min(minn, (int) c[j]);
            if(minn>next_-i) 
            {
                int j = i;
                for(; j<n&&s[j]!='_'; j++) res[j]='_';
                i=j;
                continue;
            }
        } else xpos=res[i-1]=='X'||res[i-1]=='?';


        if(xpos) res[i]='X';
        if(_pos) res[i]='_';
        if(_pos)  res[i]='?';
    }
    return res;
}

Compilation message (stderr)

paint.cpp: In function 'std::vector<long long int> solve(std::string, std::vector<int>)':
paint.cpp:23:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if(curc!=c.size()&&i+1-c[curc]>lasttakeni+1&&pref[i]-((i-c[curc]<0)?0:pref[i-c[curc]])==0)
      |            ~~~~^~~~~~~~~~

• Subtask 1: 7 / 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