Submission #949419

#	Time	Username	Problem	Language	Result	Execution time	Memory
949419		vjudge1	Painting Walls (APIO20_paint)	C++17	63 / 100	639 ms	524288 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;
    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++){
            if(pf[i-1].sz==0 || v[c[i]].sz==0)break;
            ll x=0,y=0;
            if(pf[i-1].bc==m-1 && v[c[i]][0]==0)pf[i].pb(0);
            while(x<pf[i-1].sz && y<v[c[i]].sz){
                if(pf[i-1][x]+1>v[c[i]][y])y++;
                else if(pf[i-1][x]+1<v[c[i]][y])x++;
                else{
                    pf[i].pb(v[c[i]][y]);
                    x++;
                    y++;
                }
            }
        }
        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--){
            if(sf[i+1].sz==0 || v[c[i]].sz==0)break;
            ll x=0,y=0;
            while(y<v[c[i]].sz && x<sf[i+1].sz){
                if(sf[i+1][x]-1>v[c[i]][y])y++;
                else if(sf[i+1][x]-1<v[c[i]][y])x++;
                else{
                    sf[i].pb(v[c[i]][y]);
                    x++;
                    y++;
                }
            }
            if(v[c[i]].bc==m-1 && sf[i+1][0]==0)sf[i].pb(m-1);
        }
    }
    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;
        if(pf[l+m-1].sz==0 || sf[l].sz==0){l--;continue;}
        ll x=0,y=0;
        if(pf[l+m-1].bc==m-1 && sf[l][0]==0){ans++;l+=m;continue;}
        while(x<pf[l+m-1].sz && y<sf[l].sz){
            if(pf[l+m-1][x]+1>sf[l][y])y++;
            else if(pf[l+m-1][x]+1<sf[l][y])x++;
            else{
                f=1;
                break;
            }
        }
        if(!f) l--;
        else {ans++;l+=m;}
    }
    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:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             while(x<pf[i-1].sz && y<v[c[i]].sz){
      |                    ^
paint.cpp:49:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             while(x<pf[i-1].sz && y<v[c[i]].sz){
      |                                    ^
paint.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             while(y<v[c[i]].sz && x<sf[i+1].sz){
      |                    ^
paint.cpp:64:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             while(y<v[c[i]].sz && x<sf[i+1].sz){
      |                                    ^
paint.cpp:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         while(x<pf[l+m-1].sz && y<sf[l].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 |         while(x<pf[l+m-1].sz && y<sf[l].sz){
      |                                  ^

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