oj.uz

Submission #977283

# Submission time Handle Problem Language Result Execution time Memory
977283 2024-05-07T16:05:44 Z kwongweng Painting Walls (APIO20_paint) C++17
0 / 100
 0 ms 348 KB 
#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef vector<vector<ll>> vll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define ms memset
#define fi first
#define se second

int minimumInstructions(int N, int M, int K, vi C, vi A, vector<vi> B) {
  vi col[K]; // col[i] contains indices of contractors who like colour i
  FOR(i,0,M){
    FOR(j,0,A[i]){
      col[B[i][j]].pb(i);
    }
  }
  vi pos(N); //pos[i]=1 iff it's possible to colour positions i,i+1,...,i+M-1
  vii len(M); 
  ROF(i,N-1,0){
    //makes len[u] = max length of segment that can be covered if contractor u colours i, u+1 colours i+1 and so on
    int sz = col[C[i]].size();
    vii val(sz); FOR(j,0,sz){
      int u = (col[C[i]][j]+1)%M;
      val[j] = len[u];
    }
    FOR(j,0,sz){
      //iterating contractors who like colour C[i]
      int u = col[C[i]][j];
      if (val[j].se != i+1){
        len[u] = {1,i}; //nxt cannot colour i+1
      }else{
        len[u] = {min(val[j].fi+1,M),i};
      }
      if (len[u].fi == M) pos[i]=1; //no overflow since this can only activate when i<N-M
    }
  }
  //FOR(i,0,N-M+1) cout<<pos[i]<<" "; cout<<"\n";
  if (!pos[0] || !pos[N-M]) return -1;
  int cur = 0, nxt = -1, cnt=1;
  FOR(i,1,N+1){
    if (i-cur>M){
      if (nxt==-1) return -1;
      cur = nxt; cnt++; nxt=-1;
      continue; 
    }
    if (pos[i]){
      nxt=i;
    }
  }
  return cnt;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -