oj.uz

Submission #391920

# Submission time Handle Problem Language Result Execution time Memory
391920 2021-04-20T07:34:25 Z flappybird Painting Walls (APIO20_paint) C++14
0 / 100
 8 ms 9804 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9804 KB Output is correct
2 Correct 7 ms 9804 KB Output is correct
3 Correct 7 ms 9796 KB Output is correct
4 Correct 6 ms 9724 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Incorrect 6 ms 9804 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9804 KB Output is correct
2 Correct 7 ms 9804 KB Output is correct
3 Correct 7 ms 9796 KB Output is correct
4 Correct 6 ms 9724 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Incorrect 6 ms 9804 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9804 KB Output is correct
2 Correct 7 ms 9804 KB Output is correct
3 Correct 7 ms 9796 KB Output is correct
4 Correct 6 ms 9724 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Incorrect 6 ms 9804 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9804 KB Output is correct
2 Correct 7 ms 9804 KB Output is correct
3 Correct 7 ms 9796 KB Output is correct
4 Correct 6 ms 9724 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Incorrect 6 ms 9804 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9804 KB Output is correct
2 Correct 7 ms 9804 KB Output is correct
3 Correct 7 ms 9796 KB Output is correct
4 Correct 6 ms 9724 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Incorrect 6 ms 9804 KB Output isn't correct
7 Halted 0 ms 0 KB -