Submission #949396

#	Time	Username	Problem	Language	Result	Execution time	Memory
949396		ReLice	Painting Walls (APIO20_paint)	C++14	63 / 100	1548 ms	442368 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define ll int
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
int minimumInstructions(int n, int m, int k, vll c, vll a, vector<vll> b) {
    vector<vll> v(k);
    ll i,j;
    for(i=0;i<m;i++){
        for(j=0;j<a[i];j++){
            v[b[i][j]].pb(i);
        }
    }
    ll l=0,ans=0,mx=-1;
    map<ll,ll> mp;
    vector<vll> pf(n),sf(n);
    for(l=0;l<n;l+=m){
        for(auto j : v[c[l]]) pf[l].pb(j);
        for(i=l+1;i<=min(n-1,l+m-1);i++){
            for(j=0;j<v[c[i]].sz;j++){
                if(!pf[i-1].sz)break;
                ll low=lb(all(pf[i-1]),(v[c[i]][j]-1+m)%m)-pf[i-1].begin();
                if(low!=pf[i-1].sz && (v[c[i]][j]-1+m)%m==pf[i-1][low]) pf[i].pb(v[c[i]][j]);
            }
        }
        if(l+m-1>=n) break;
        for(auto j : v[c[l+m-1]]) sf[l+m-1].pb(j);
        for(i=l+m-2;i>=l;i--){
            for(j=0;j<v[c[i]].sz;j++){
                if(!sf[i+1].sz)break;
                ll low=lb(all(sf[i+1]),(v[c[i]][j]+1)%m)-sf[i+1].begin();
                if(low!=sf[i+1].sz && (v[c[i]][j]+1)%m==sf[i+1][low]) sf[i].pb(v[c[i]][j]);
            }
        }
    }
    l=0;
    mp[-1]++;
    while(l<n){
        if(mp[l])return -1;
        mp[l]++;
        if(l+m-1>=n){l--;continue;}
        if(l%m==0){
            if(sf[l].sz){
                ans++;
                l+=m;
            }else l--;
            continue;
        }
        ll f=0;
        for(auto i : pf[l+m-1]){
            ll low=lb(all(sf[l]),(i+1)%m)-sf[l].begin();
            if(low!=sf[l].sz && sf[l][low]==(i+1)%m){
                ans++;
                l+=m;
                f=1;
                break;
            }
        }
        if(!f) l--;
    }
    return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(j=0;j<v[c[i]].sz;j++){
      |                      ^
paint.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                 if(low!=pf[i-1].sz && (v[c[i]][j]-1+m)%m==pf[i-1][low]) pf[i].pb(v[c[i]][j]);
      |                       ^
paint.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(j=0;j<v[c[i]].sz;j++){
      |                      ^
paint.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                 if(low!=sf[i+1].sz && (v[c[i]][j]+1)%m==sf[i+1][low]) sf[i].pb(v[c[i]][j]);
      |                       ^
paint.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |             if(low!=sf[l].sz && sf[l][low]==(i+1)%m){
      |                   ^
paint.cpp:40:18: warning: unused variable 'mx' [-Wunused-variable]
   40 |     ll l=0,ans=0,mx=-1;
      |                  ^~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 0 / 37