oj.uz

Submission #965944

# Submission time Handle Problem Language Result Execution time Memory
965944 2024-04-19T08:28:09 Z willychan Painting Walls (APIO20_paint) C++17
0 / 100
 1 ms 348 KB 
#include "paint.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int minimumInstructions(int N, int M, int K, std::vector<int> C,std::vector<int> A, std::vector<std::vector<int>> B) {
  vector<int> ok(N,0);
  vector<int> mp(K,-1);
  for(int i=0;i<M;i++){
  	for(int j=0;j<A[i];j++)	{
		mp[B[i][j]]=i;
	}
  }
  assert(M!=1);
  for(int i=0;i<N;i++){
  	C[i] = mp[C[i]];
  }
  vector<int> gnext(N-1,0);
  for(int i=0;i<N-1;i++) {
  	gnext[i] = (C[i]+1)%M==C[i+1];
	if(C[i]==-1 || C[i+1]==-1) gnext[i]=0;
  }
  int head = 0;
  int ocnt=0;
  for(int i=0;i<=N-M;i++){
  	while(head<=i+M-2){
		ocnt+=(gnext[head])	;
		head++;
	}
	if(ocnt==M-1) ok[i]=1;
	ocnt-=gnext[i];
  }
  /*
  for(int i=0;i<=N-M;i++){
	for(int j=0;j<M;j++){
  		bool work=1;
		for(int k=0;k<M;k++){
			int f = lower_bound(B[(j+k)%M].begin(),B[(j+k)%M].end(),C[i+k])-B[(j+k)%M].begin();
			work&=(f<A[(j+k)%M] && B[(j+k)%M][f]==C[i+k]);
		}
		if(work){
			ok[i]=1;
			break;
		}
	}
  }
  */
  int cur = 0;
  int ans = 0;
  vector<bool> colored(N,0);
  int maxn = -1e9;
  for(int i=0;i<N;i++){
  	if(ok[i]) maxn = max(maxn,i);
	if(!colored[i]){
		ans++;
		int k = maxn+M-1;
		if(k<i) return -1;
		for(int h=i;h<=k;h++) colored[h]=1;
	}
  }
  return ans;
}

Compilation message

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:48:7: warning: unused variable 'cur' [-Wunused-variable]
   48 |   int cur = 0;
      |       ^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -