Submission #934337

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
934337	2024-02-27T07:33:02 Z	irmuun	Painting Walls (APIO20_paint)	C++17	Compilation error	0 ms	0 KB

paint

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
 
int minimumInstructions(int n,int m,int k,vector<int>C,vector<int>A,vector<vector<int>>B){
    vector<int>cnt(k,0);
    int mx=0;
    for(int i=0;i<m;i++){
        for(auto x:B[i]){
            cnt[x]++;
            mx=max(mx,cnt[x]);
        }
    }
    if(mx<=1){
        vector<int>can(k,-1);
        for(int i=0;i<m;i++){
            for(int j=0;j<A[i];j++){
                can[B[i][j]]=i;
            }
        }
        for(int i=0;i<n;i++){
            if(can[C[i]]==-1) return -1;
        }
        vector<int>count(n,0);
        int cur=1;
        count[n-1]=1;
        for(int i=n-2;i>=0;i--){
            if(can[C[i]]==can[C[i+1]]-1||(can[C[i+1]]==0&&can[C[i]]==m-1)){
                cur++;
            }
            else{
                cur=1;
            }
            count[i]=cur;
        }
        int ans=0;
        bool ok=true;
        if(count[0]<m) return -1;
        ans++;
        int r=m-1,nxt=0;
        for(int i=1;i<n;i++){
            if(count[i]>=m){
                nxt=i;
            }
            if(i>r){
                r=nxt+m-1;
                if(i>r) return -1;
                ans++;
            }
        }
        return ans;
    }
    vector<vector<bool>>have(k,vector<bool>(m,0));
    for(int i=0;i<m;i++){
        for(auto x:B[i]){
            have[x][i]=true;
        }
    }
    vector<int>q(m),q1;
    for(int j=0;j<m;j++){
        if(have[C[i]][j]==false){
            q[i][j]=-1e9;
        }
        else if(i==n-1||have[C[i+1]][(j+1)%m]==false){
            q[i][j]=1;
        }
        else{
            q[i][j]=q[i+1][(j+1)%m]+1;
        }
    }
    for(int i=n-2;i>=0;i--){
        q1=q;
        for(int j=0;j<m;j++){
            if(have[C[i]][j]==false){
                q[i][j]=-1e9;
            }
            else if(i==n-1||have[C[i+1]][(j+1)%m]==false){
                q[i][j]=1;
            }
            else{
                q[i][j]=q1[i+1][(j+1)%m]+1;
            }
        }
    }
    vector<int>mn(n+1,1e9);
    mn[n]=0;
    multiset<int>st;
    for(int i=n-m+1;i<=n;i++){
        st.insert(mn[i]);
    }
    for(int i=n-m;i>=0;i--){
        bool ok=false;
        for(int j=0;j<m;j++){
            if(q[i][j]>=m){
                ok=true;
                break;
            }
        }
        if(ok){
            mn[i]=*st.begin()+1;
        }
        st.erase(st.find(mn[i+m]));
        st.insert(mn[i]);
    }
    if(mn[0]>=1e9) return -1;
    return mn[0];
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:44:14: warning: unused variable 'ok' [-Wunused-variable]
   44 |         bool ok=true;
      |              ^~
paint.cpp:68:19: error: 'i' was not declared in this scope
   68 |         if(have[C[i]][j]==false){
      |                   ^
paint.cpp:82:21: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}[int]' for array subscript
   82 |                 q[i][j]=-1e9;
      |                     ^
paint.cpp:85:21: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}[int]' for array subscript
   85 |                 q[i][j]=1;
      |                     ^
paint.cpp:88:21: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}[int]' for array subscript
   88 |                 q[i][j]=q1[i+1][(j+1)%m]+1;
      |                     ^
paint.cpp:88:32: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}[int]' for array subscript
   88 |                 q[i][j]=q1[i+1][(j+1)%m]+1;
      |                                ^
paint.cpp:101:20: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type {aka int}[int]' for array subscript
  101 |             if(q[i][j]>=m){
      |                    ^