oj.uz

Submission #1069370

# Submission time Handle Problem Language Result Execution time Memory
1069370 2024-08-21T20:35:15 Z pawned Painting Walls (APIO20_paint) C++17
0 / 100
 0 ms 344 KB 
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")

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

#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

#include "paint.h"

int minimumInstructions(int N, int M, int K, vi C, vi A, vector<vi> B) {
	vi use(K, -1);
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < A[i]; j++) {
			use[B[i][j]] = i;
		}
	}
/*	cout<<"use: ";
	for (int x : use)
		cout<<x<<" ";
	cout<<endl;*/
	vi valr(N, -1);
	for (int i = 0; i < N; i++) {
		valr[i] = use[C[i]];
	}
/*	cout<<"valr: ";
	for (int x : valr)
		cout<<x<<" ";
	cout<<endl;*/
	vi diff(N - 1, 0);
	vi is1(N - 1, 0);	// 1 if diff[i] is 1; 0 otherwise
	for (int i = 0; i < N - 1; i++) {
		if (valr[i] != -1 && valr[i + 1] != -1) {
			diff[i] = valr[i + 1] - valr[i];
			diff[i] %= M;
			diff[i] += M;
			diff[i] %= M;
			if (diff[i] == 1 || M == 1)
				is1[i] = 1;
		}
	}
/*	cout<<"diff: ";
	for (int x : diff)
		cout<<x<<" ";
	cout<<endl;*/
	vi pfs(N, 0);
	pfs[0] = 0;
	for (int i = 1; i < N; i++) {
		pfs[i] = pfs[i - 1] + is1[i - 1];
	}
/*	cout<<"pfs: ";
	for (int x : pfs)
		cout<<x<<" ";
	cout<<endl;*/
	vector<bool> cfill(N - M + 1, false);
	for (int i = 0; i < N - M + 1; i++) {
		if (pfs[i + M - 1] - pfs[i] == M - 1)
			cfill[i] = true;
	}
/*	cout<<"cfill: ";
	for (bool b : cfill)
		cout<<b<<" ";
	cout<<endl;*/
	set<int> good;
	for (int i = 0; i < N - M + 1; i++) {
		if (cfill[i])
			good.insert(i);
	}
	good.insert(-M);
	good.insert(N);
	int curr = -M;
	int total = 0;
	while (curr < N) {
		auto it = good.lower_bound(curr + M + 1);
		if (it == good.begin())
			return -1;
		int newc = *(--it);
		if (newc == curr)
			return -1;
		curr = newc;
		total++;
	}
	total--;
	return total;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 37.0

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