Submission #437555

#	Time	Username	Problem	Language	Result	Execution time	Memory
437555		Sohsoh84	Painting Walls (APIO20_paint)	C++14	40 / 100	1558 ms	37936 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 2e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int n, m, k, C[MAXN];
vector<int> L[MAXN];
unordered_map<int, int, custom_hash> W[2]; 
ll dp[MAXN];

int minimumInstructions(
	int N, int M, int K, std::vector<int> tC,
	std::vector<int> tA, std::vector<std::vector<int>> tB) {
	
	n = N, m = M, k = K;
	for (int i = 0; i < n; i++) C[i] = tC[i];
	for (int i = 0; i < m; i++)
		for (int e : tB[i])
		       L[e].push_back(i);	
	
	set<pll> dp_st;
	dp_st.insert({0, n});

	for (int i = n - 1; i >= 0; i--) {
		int ind = i & 1;
		W[ind].clear();
		dp[i] = INF;
					
		dp_st.erase({dp[i + m + 1], i + m + 1});
		ll t = dp_st.begin() -> X;

		for (int p : L[C[i]]) {
			int l = W[ind][p] = W[1 - ind][(p + 1) % m] + 1;
			if (l >= m) dp[i] = t + 1;
		}
		
		dp_st.insert({dp[i], i});
	}

	if (dp[0] >= INF) return -1;
	return dp[0];
}

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