Submission #535873

#	Time	Username	Problem	Language	Result	Execution time	Memory
535873		mario05092929	Painting Walls (APIO20_paint)	C++17	100 / 100	949 ms	505672 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair <int,int> pi;
typedef vector <int> vec;
const int INF = 1e9;
int n,m,k;
int a[100005],d[100005],ok;
vector <int> rc[100005];
vector <pi> c[100005];
vector <int> id[100005];
multiset <int> s;
pi ch[100005];
int cnt;

int minimumInstructions(int N,int M,int K,vec C,vec A,vector<vec> B) {
    n = N, m = M, k = K;
    int i,ok,wh,j,it;
    for(i = 1;i <= n;i++) a[i] = C[i-1];
    for(i = 0;i < m;i++) {
        for(j = 0;j < B[i].size();j++) {
            rc[B[i][j]].push_back(i);
            cnt++;
        }
    }
    for(i = 1;i <= n;i++) {
        c[i].resize(rc[a[i]].size());
        for(j = 0;j < rc[a[i]].size();j++) {
            c[i][j] = {rc[a[i]][j],0};
            cnt += 2;
        }
    }
    if(cnt >= 200000000) while(1);
    for(i = 1;i <= n;i++) {
        ok = 0;
        for(j = 0;j < c[i].size();j++) {
            wh = (c[i][j].x+m-1)%m;
            if(ch[wh].x == i) c[i][j].y = c[i-1][ch[wh].y].y+1;
            else c[i][j].y = 1;
            if(c[i][j].y >= m) ok = 1;
        }
        for(j = 0;j < c[i].size();j++) {
            ch[c[i][j].x] = {i+1,j};
        }
        d[i] = INF;
        if(ok) {
            if(i-m < 1) d[i] = 1;
            else {
                it = *s.begin();
                d[i] = it+1;
                if(d[i] >= INF) return -1;
            }
        }
        if(i-m >= 1) s.erase(s.find(d[i-m]));
        s.insert(d[i]);
    }
    if(d[n] >= INF) return -1;
    return d[n];
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, vec, vec, std::vector<std::vector<int> >)':
paint.cpp:24:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         for(j = 0;j < B[i].size();j++) {
      |                   ~~^~~~~~~~~~~~~
paint.cpp:31:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(j = 0;j < rc[a[i]].size();j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
paint.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(j = 0;j < c[i].size();j++) {
      |                   ~~^~~~~~~~~~~~~
paint.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(j = 0;j < c[i].size();j++) {
      |                   ~~^~~~~~~~~~~~~

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