Submission #502784

#	Time	Username	Problem	Language	Result	Execution time	Memory
502784		Victor	Painting Walls (APIO20_paint)	C++17	Compilation error	0 ms	0 KiB

paint

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const int INF = 1'000'000'007;

int n,m,k;
vvi people;
uset<int> colors[100005];
vi wall;
set<int>possible;

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
    people.swap(B);
    wall.swap(C);
    n=N,m=M,k=K;

    rep(i,0,m) trav(color,people[i]) colors[color].insert(i);
    for(int pos=m-1;pos<n;pos+=m) {
        int cur_color=wall[pos];

        trav(person,colors[cur_color]) {
            int first_person=(person+1)%m,num_match=0;
            int start_pos=pos-m+1;
            rep(i,0,m-1) num_match+=colors[wall[start_pos+i]].count((first_person+i)%m);

            rep(i,m-1,m-1+(n-pos)){
                num_match+=colors[wall[start_pos+m-1]].count((first_person-1+m)%m);
                if(num_match==m) possible.insert(start_pos);
                
                num_match-=colors[wall[start_pos]].count(first_person);
                first_person=(first_person+1)%m;
                ++start_pos;
            }
        }
    }

    //cout<<sz(possible)<<endl;
    possible.insert(-INF);
    int pos=0,ans=0;
    while(pos<n) {
        auto it=possible.upper_bound(pos);
        --it;
        if(*it+m>pos) {
            pos=*it+m;
            ++ans;

        } else return -1;
    }
    return ans;
}

int main() {
    int N, M, K;
    assert(3 == scanf("%d %d %d", &N, &M, &K));

    std::vector<int> C(N);
    for (int i = 0; i < N; ++i) {
        assert(1 == scanf("%d", &C[i]));
    }

    std::vector<int> A(M);
    std::vector<std::vector<int>> B(M);
    for (int i = 0; i < M; ++i) {
        assert(1 == scanf("%d", &A[i]));
        B[i].resize(A[i]);
        for (int j = 0; j < A[i]; ++j) {
            assert(1 == scanf("%d", &B[i][j]));
        }
    }

    int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
    printf("%d\n", minimum_instructions);

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccrQA7ss.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccpnbxis.o:paint.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status