Submission #391920

#	Time	Username	Problem	Language	Result	Execution time	Memory
391920		flappybird	Painting Walls (APIO20_paint)	C++14	0 / 100	8 ms	9804 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define MAX 202020
//0-based index를 사용
//i번 회전 -> i번째 사람이 맨 앞으로 오도록 하는 것(실제 의미와 다름)
bool rksmd[MAX]; //[i-M+1, i]를 칠하는것이 "가능"한지 저장
ll rodtls[MAX]; //j번 회전했을때 첫번째 값이 맞았던 최근 인덱스를 저장(마지막으로 dp가 "갱신"된 for문의 i시점)
ll dp[MAX]; //for 문 i번째 실행했을때 dp[j]=k : i-1번째 상황에서 j번 돌려서 색칠하게 했을때 오른쪽에서 k번째에 터진다.
set<ll> tor[MAX]; // i번째 "색"을 칠할 수 있는 사람의 세트
bool exist(const set<ll>& s, ll x) {
	return s.find(x) != s.end();
}
//"이전" 사람이 누구인지 반환
ll dlwjs(ll x, ll M) {
	if (x == 0) return M - 1;
	else return x - 1;
}
int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	ll i;
	for (i = 0; i < M; i++) for (auto x : B[i]) tor[x].insert(i);
	//[i-M+1, i]을 확인, 음수인 곳은 아무도 못 칠한다 가정
	for (i = 0; i <= M; i++) rodtls[i] = -1;
	for (i = 0; i < N; i++) {
		vector<pair<ll, ll>> memo; //i번째 시점에 dp를 갱신한 k만 저장
		for (auto k : tor[C[i]]) {
			//갱신 가능한 경우 : 바로 전 항목이 전 사람에 의해 갱신된 경우
			if (rodtls[dlwjs(k, M)] == i - 1) memo.push_back({ k, dp[dlwjs(k, M)] + 1 });
			else memo.push_back({ k, 1 });
		}
		for (auto a : memo) rodtls[a.first] = i, dp[a.first] = a.second;
		for (auto a : memo) if (a.second >= M) rksmd[i] = 1;
	}
	ll cnt = 0;
	ll mx = -1;
	ll lim = -1;
	for (i = M - 1; i < N; i++) {
		if (rksmd[i]) mx = i;
		if (lim < i) {
			lim = mx + M - 1;
			cnt++;
			if (lim < i) return -1;
		}
	}
	return cnt;
}

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