Submission #1193580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193580		vyaduct	Painting Walls (APIO20_paint)	C++20	Compilation error	0 ms	0 KiB

paint

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define vt vector
#define F first
#define S second
#define pii pair<ll,ll>
#define pb push_back

int subtask1(int n, int m, vt<int> &C, vt<ll> &pos){
   for (int i=1;i<n;i++){
    int a = pos[C[i-1]];
    int b = pos[C[i]];
    if (a == m-1) {
      if (b != 0) return -1;
    } else {
      if (b != a+1) return -1;
    }
  }
  return (n+m-1)/m;
}

bool valid(int i, int j, int m){
  return (i+1)%m == j;
}

// returns if there is i,j in L,R such that valid(i,j) = true
// aka, can we go from C[i] to C[j]
// O(|L| log (|R|))
bool ok(set<ll> &L, set<ll> &R, ll m){
  for (auto x: L){
    int y = (x+1)%m;
    if (R.count(y)) return true;
  }
  return false;
}

vt<pii> runlen(vt<bool> a){
  vt<pii> res;
  ll cnt=1, last = a[0];
  for (int i=1;i<a.size();i++){
    if (a[i] == last) cnt++;
    else {
      res.pb({last, cnt});
      cnt = 1;
      last = a[i];
    }
  }
  res.pb({last, cnt});
  return res;
}

int minimumInstructions(int n, int m, int k, vt<int> C, vt<int> A, vt<vt<int>> B){
  bool s1=true;
  vt<ll> fpos(k, -1);
  vt<set<ll>> pos(k);
  for (int i=0;i<m;i++){
    for (auto x: B[i]){
      if (fpos[x] != -1) s1 = false;
      fpos[x] = i;
      pos[x].insert(i);
    }
  }
  if (s1) return subtask1(n, m, C, fpos);

  // window movement
  vt<bool> V;
  for (ll i=0;i+1<n;i++){
    auto sa = pos[C[i]];
    auto sb = pos[C[i+1]];
    bool flag = ok(sa, sb, m);
    V.pb(flag);
  }

  vt<pii> r = runlen(V);

  ll cnt=1e9;
  for (int j=0;j<sz(r);j++){
    ll cur=0;
    int mm = sz(r);
    int i = j % mm;
    while(mm--){
      int x = r[i].F, c = r[i].S;
      int cc = c+1;
      if (x == 0 && cc>= m) {cur = -1; break;}
      if (x==1) cur += (cc+m-1)/m;
      i = (i+1) % sz(r);
    }
    if (cur != -1) cnt = min(cnt, cur);
  }
  return (cnt == 1e9 ? -1 : cnt);
}

void solve(){
  int n, m, k;
  cin>>n>>m>>k;
  
  vt<int> C(n);
  for (int i=0;i<n;++i) cin>>C[i];
  
  vt<int> A(m);
  vt<vt<int>> B(m);
  for (int i=0;i<m;++i) {
    cin>>A[i];
    B[i].resize(A[i]);
    for (int j=0;j<A[i];++j) {
      cin>>B[i][j];
    }
  }

  int ans = minimumInstructions(n, m, k, C, A, B);
  cout << ans << endl;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();
  return 0;
}

Compilation message (stderr)

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