Submission #676525

#	Time	Username	Problem	Language	Result	Execution time	Memory
676525		NothingXD	Painting Walls (APIO20_paint)	C++17	63 / 100	1588 ms	13332 KiB

paint

#include "paint.h"

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

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
/*typedef __uint128_t L;
struct FastMod {
	ull b, m;
	FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}
	ull reduce(ull a) {
		ull q = (ull)((L(m) * a) >> 64);
		ull r = a - q * b; // can be proven that 0 <= r < 2*b
		return r >= b ? r - b : r;
	}
};
FastMod FM(2);*/
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << H;
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
#define F first
#define S second

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;
const int maxk = 2e3 + 10;
int n, m, k, dp[2][maxk], a[maxn];
vector<int> idx[maxn];
bool mark[maxn];

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
	n = N;
	m = M;
	k = K;
	for (int i = 1; i <= n; i++) a[i] = C[i-1]+1;
	for (int i = 0; i < m; i++){
		for (auto x: B[i]){
			idx[x+1].push_back(i+1);
			idx[x+1].push_back(m+i+1);
		}
	}
	for (int i = 1; i <= k; i++){
		sort(all(idx[i]));
	}
	for (int i = n; i; i--){
		int ptr = i&1;
		int prv = 1 - ptr;
		int sz = idx[a[i]].size();
		for (int j = 0; j < sz; j++){
			dp[ptr][j] = 0;
			if (i == n) continue;
			int x = idx[a[i]][j];
			int y = upper_bound(all(idx[a[i+1]]), x) - idx[a[i+1]].begin();
			if (y == idx[a[i+1]].size() || idx[a[i+1]][y] != x + 1) continue;
			dp[ptr][j] = dp[prv][y];
		}
		for (int j = 0; j < sz; j++){
			dp[ptr][j]++;
			if (dp[ptr][j] >= m) mark[i] = true;
		}
	}
	int ans = 0;
	int ptr = 1;
	queue<int> q;
	if (mark[1]) q.push(1);
	while(ptr <= n){
		while(!q.empty() && q.front() + m <= ptr) q.pop();
		if (q.empty()) return -1;
		ans++;
		int tmp = q.back();
		while(ptr <= n && ptr < tmp + m){
			ptr++;
			if (mark[ptr]) q.push(ptr);
		}
	}
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:70:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    if (y == idx[a[i+1]].size() || idx[a[i+1]][y] != x + 1) continue;
      |        ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 0 / 37