Submission #292949

#	Time	Username	Problem	Language	Result	Execution time	Memory
292949		arnold518	Painting Walls (APIO20_paint)	C++14	63 / 100	1579 ms	16320 KiB

paint

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

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

const int INF = 1e9;

const int MAXN = 1e5;
const int MAXM = 5e4;
const int MAXK = 1e5;

int N, M, K;
int C[MAXN+10], A[MAXM+10];
vector<int> B[MAXM+10];
vector<int> D[MAXK+10];
int dp[MAXN+10];
int P[MAXM+10];

struct dequeue
{
	int pt=0;
	vector<int> V;
	void push_back(int x) { V.push_back(x); }
	void pop_back() { V.pop_back(); }
	void pop_front() { pt++; }
	int front() { return V[pt]; }
	int back() { return V.back(); }
	bool empty() { return pt==V.size(); }
};

int minimumInstructions(int _N, int _M, int _K, vector<int> _C, vector<int> _A, vector<vector<int>> _B)
{
	N=_N; M=_M; K=_K;
	for(int i=1; i<=N; i++) C[i]=_C[i-1];
	for(int i=0; i<M; i++) A[i]=_A[i];
	for(int i=0; i<M; i++) B[i]=_B[i];

	for(int i=0; i<M; i++)
	{
		for(auto it : B[i])
		{
			D[it].push_back(i);
		}
	}

	for(int i=1; i<=N; i++) if(D[C[i]].empty()) return -1;

	for(int i=1; i<M; i++)
	{
		for(auto it : D[C[i]])
		{
			P[((it-i)%M+M)%M]++;
		}
	}

	int cnt=0;
	for(int i=0; i<M; i++) if(P[i]==M) cnt++;

	dequeue DQ;
	for(int i=1; i<=N; i++) dp[i]=INF;

	DQ.push_back(0); DQ.push_back(M-1);
	for(int i=M; i<=N; i++)
	{
		if(i!=M) for(auto it : D[C[i-M]])
		{
			if(P[((it-i)%M+M)%M]==M) cnt--;
			P[((it-i)%M+M)%M]--;
		}
		for(auto it : D[C[i]])
		{
			P[((it-i)%M+M)%M]++;
			if(P[((it-i)%M+M)%M]==M) cnt++;
		}
		
		while(!DQ.empty() && DQ.front()<i-M) DQ.pop_front();
		if(cnt && dp[DQ.front()]!=INF) dp[i]=dp[DQ.front()]+1;
		while(!DQ.empty() && dp[DQ.back()]>=dp[i]) DQ.pop_back();
		DQ.push_back(i);
	}

	if(dp[N]==INF) return -1;
	else return dp[N];
}

Compilation message (stderr)

paint.cpp: In member function 'bool dequeue::empty()':
paint.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  bool empty() { return pt==V.size(); }
      |                        ~~^~~~~~~~~~

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