Submission #949359

#	Time	Username	Problem	Language	Result	Execution time	Memory
949359		ReLice	Painting Walls (APIO20_paint)	C++14	63 / 100	1564 ms	504084 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),cur(n);
    while(l<n){
        if(mp[l] || l<0) return -1;
        mp[l]++;
        if(l+m-1>=n) {l--;continue;}
        vll vv,nv;
        for(auto i : v[c[l+m-1]])vv.pb(i);
        cur[l+m-1]=vv;
        for(i=l+m-2;i>mx;i--){
            if(vv.sz==0 || v[c[i]].sz==0)break;
            ll x=lb(all(vv),v[c[i]][0]+1)-vv.begin(),y=0;
            bool f=1;
            while(y<v[c[i]].sz && (f || x<vv.sz)){
                if(f && x==vv.sz){f=0;x%=vv.sz;}
                if((vv[x]-1+m)%m>v[c[i]][y])y++;
                else if((vv[x]-1+m)%m<v[c[i]][y])x++;
                else{
                    nv.pb(v[c[i]][y]);
                    x++;
                    y++;
                }
            }
            vv=nv;
            cur[i]=vv;
            nv.clear();
        }

        if(mx>=0 && mx>=l){
            if(!pf[l].sz || !vv.sz){l--;continue;}
            ll x=lb(all(vv),(pf[l][0]+(mx-l+1))%m)-vv.begin(),y=0;
            bool f=1;
            while(y<v[c[i]].sz && (f || x<vv.sz)){
                if(f && x==vv.sz){f=0;x%=vv.sz;}
                if((vv[x]-(mx-l+1)+m)%m>pf[l][y])y++;
                else if((vv[x]-(mx-l+1)+m)%m<pf[l][y])x++;
                else{
                    nv.pb(pf[l][y]);
                    x++;
                    y++;
                }
            }
            vv=nv;
            if(vv.sz){
                cur[l]=vv;
                nv.clear();
                vv=cur[mx+1];
                for(i=mx;i>l;i--){
                    if(vv.sz==0 || pf[i].sz==0)break;
                    ll x=lb(all(vv),pf[i][0]+1)-vv.begin(),y=0;
                    bool f=1;
                    while(y<pf[i].sz && (f || x<vv.sz)){
                        if(f && x==vv.sz){f=0;x%=vv.sz;}
                        if((vv[x]-1+m)%m>pf[i][y])y++;
                        else if((vv[x]-1+m)%m<pf[i][y])x++;
                        else{
                            nv.pb(pf[i][y]);
                            x++;
                            y++;
                        }
                    }
                    vv=nv;
                    cur[i]=vv;
                    nv.clear();
                }
            }

        }

        if(vv.sz) {
            for(i=l ;i<=l+m-1;i++)pf[i]=cur[i];
            mx=l+m-1;
            ans++;l+=m;
        }
        else 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:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while(y<v[c[i]].sz && (f || x<vv.sz)){
      |                    ^
paint.cpp:54:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             while(y<v[c[i]].sz && (f || x<vv.sz)){
      |                                          ^
paint.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                 if(f && x==vv.sz){f=0;x%=vv.sz;}
      |                          ^
paint.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             while(y<v[c[i]].sz && (f || x<vv.sz)){
      |                    ^
paint.cpp:73:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             while(y<v[c[i]].sz && (f || x<vv.sz)){
      |                                          ^
paint.cpp:74:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 if(f && x==vv.sz){f=0;x%=vv.sz;}
      |                          ^
paint.cpp:92:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                     while(y<pf[i].sz && (f || x<vv.sz)){
      |                            ^
paint.cpp:92:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                     while(y<pf[i].sz && (f || x<vv.sz)){
      |                                                ^
paint.cpp:93:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                         if(f && x==vv.sz){f=0;x%=vv.sz;}
      |                                  ^

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