Submission #568276

#	Time	Username	Problem	Language	Result	Execution time	Memory
568276		Zanite	벽 칠하기 (APIO20_paint)	C++17	100 / 100	773 ms	14380 KiB

paint

// You can't change other people; you can only change yourself.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#include "paint.h"

// Pragmas
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// Namespaces
#define yume using
#define wo namespace
#define kanaeyo std
#define nazotte __gnu_pbds
yume wo kanaeyo;
yume wo nazotte;

// Data types
using i8	= __int128;
using ll	= long long;
using si	= short int;
using ld	= long double;

// Pairs
using pi8	= pair<i8, i8>;
using pll	= pair<ll, ll>;
using pii	= pair<int, int>;
using psi	= pair<si, si>;
using pld	= pair<ld, ld>;
#define fi first
#define se second

// PBDS
template<typename T>
using ordered_set	= tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

// Quick macro functions
#define sqr(x) ((x)*(x))
#define pow2(x) (1ll << (x))
#define debug(x) cout << #x << " = " << (x) << '\n'
#define debugV(x, a) cout << #x << "[" << (a) << "] = " << (x[a]) << '\n'

// Check min and max
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
 
// Modular arithmetic
template<typename T> void maddto(T &a, T b, T mod) {a += b; a %= mod;}
template<typename T> void msubto(T &a, T b, T mod) {a -= b; while (a < 0) a += mod; a %= mod;}
template<typename T> void mmulto(T &a, T b, T mod) {a *= b; a %= mod;}
 
template<typename T> T madd(T a, T b, T mod) {a += b; a %= mod; return a;}
template<typename T> T msub(T a, T b, T mod) {a -= b; while (a < 0) a += mod; return a;}
template<typename T> T mmul(T a, T b, T mod) {a *= b; a %= mod; return a;}

// Constants
const ll ModA	= 998244353;
const ll ModC	= 1e9 + 7;
const ll INF	= 1e18;
const ll iINF	= 1e9;
const ld EPS	= 1e-9;
const ld iEPS	= 1e-6;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	vector<int> contractor[K];
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < A[i]; j++) {
			contractor[B[i][j]].push_back(i);
		}
	}

	vector<bool> pos(N);
	int len[2][N];
	memset(len, 0, sizeof(len));
	
	int first = (N-1) & 1;
	vector<int> filled[2];
	for (auto x : contractor[C[N-1]]) {
		len[first][x] = 1;
		filled[first].push_back(x);
		if (len[first][x] >= M) {
			pos[N-1] = 1;
		}
	}
	for (int i = N-2; i >= 0; i--) {
		int cur = i & 1, prv = cur ^ 1;
		for (auto x : contractor[C[i]]) {
			len[cur][x] = len[prv][(x+1) % M] + 1;
			filled[cur].push_back(x);
			if (len[cur][x] >= M) {
				pos[i] = 1;
			}
		}
		for (auto f : filled[prv]) {
			len[prv][f] = 0;
		}
		filled[prv].clear();
	}
	
	vector<int> segments;
	for (int i = 0; i < N; i++) {
		if (pos[i]) {segments.push_back(i);}
	}
	segments.push_back(N);
	
	vector<int> used = {-M};
	for (auto s : segments) {
		if (s > used.back() + M) {
			return -1;
		} else {
			int us = used.size();
			if (us >= 2 && s <= used[us-2] + M) {
				used.pop_back();
			}
			used.push_back(s);
		}

		//for (auto i : used) {cout << i << ' ';}
		//cout << '\n';
	}
	return used.size()-2;
}

//int main() {}

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