Submission #949316

#	Time	Username	Problem	Language	Result	Execution time	Memory
949316		ReLice	Painting Walls (APIO20_paint)	C++14	63 / 100	1571 ms	12628 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;
    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]])vv.pb(i);
        for(i=l+1;i<=l+m-1;i++){
            if(vv.sz==0)break;
            ll x=0,y=0;
            if(vv.bc==m-1 && v[c[i]].sz && v[c[i]][0]==0)nv.pb(0);
            if(vv.sz<v[c[i]].sz){
                for(j=0;j<vv.sz;j++){
                    ll low=lb(all(v[c[i]]),vv[j]+1)-v[c[i]].begin();
                    if(low<v[c[i]].sz && v[c[i]][low]==vv[j]+1)nv.pb(vv[j]+1);
                }
            }else{
                for(j=0;j<v[c[i]].sz;j++){
                    ll low=lb(all(vv),v[c[i]][j]-1)-vv.begin();
                    if(low<vv.sz && vv[low]==v[c[i]][j]-1)nv.pb(v[c[i]][j]);
                }
            }
            vv=nv;
            nv.clear();
        }
        if(vv.sz) {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:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |                 for(j=0;j<vv.sz;j++){
      |                          ^
paint.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                     if(low<v[c[i]].sz && v[c[i]][low]==vv[j]+1)nv.pb(vv[j]+1);
      |                           ^
paint.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |                 for(j=0;j<v[c[i]].sz;j++){
      |                          ^
paint.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                     if(low<vv.sz && vv[low]==v[c[i]][j]-1)nv.pb(v[c[i]][j]);
      |                           ^
paint.cpp:50:16: warning: unused variable 'x' [-Wunused-variable]
   50 |             ll x=0,y=0;
      |                ^
paint.cpp:50:20: warning: unused variable 'y' [-Wunused-variable]
   50 |             ll x=0,y=0;
      |                    ^

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