oj.uz

Submission #403511

# Submission time Handle Problem Language Result Execution time Memory
403511 2021-05-13T09:02:19 Z sealnot123 Painting Walls (APIO20_paint) C++14
0 / 100
 1 ms 292 KB 
#include "paint.h"

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ROF(i,a,b) for(int i=(a); i>=(b); --i)
#define pb push_back
#define eb emplace_back
#define SZ(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define make_unique(a) sort(all((a))), (a).erase(unique(all((a))),(a).end())
#define x first
#define y second
#define MP make_pair
#define MT make_tuple
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) FOR(i,1,y) cout << "##"; cout << #x << " = " << x << endl

using namespace std;

typedef long long i64;
typedef tuple<int,int,int> iii;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long double ld;

int minimumInstructions(
    int N, int M, int K, vector<int> C,
    vector<int> A, vector<vector<int>> B) {

	vi bef(M), aft(M);
	vector<vi> color(K);

	FOR(i, 0, M-1){
		bef[i] = (i-1+M)%M;
		aft[i] = (i+1)%M;
		for(const int c : B[i]){
			color[c].eb(i);
		}
	}

	vi last(M,0);
	vi good;
	
	FOR(i, 0, N-1){
		int mx = 1;
		vector<pii> wait;
		for(const int c : color[C[i]]){
			wait.eb(c, 1);
			if(last[bef[c]] == -1) continue;
			mx = max(last[bef[c]]+1,mx);
			wait.back().y = last[bef[c]]+1;
		}
		if(i==0){
			FOR(j,0,M-1) last[j] = -1;
		}else{
			for(const int c : color[C[i-1]]){
				last[c] = -1;
			}
		}
		for(const pii e : wait){
			last[e.x] = e.y;
		}
		if(mx >= M) good.eb(i);
	}

	if(good.empty()) return -1;
	if(good.back() != N-1) return -1;

	deque<pair<int,int>> q;
	q.eb(-1, 0);
	for(const int e : good){
		//printf("good %d\n",e);
		while(!q.empty() && q.front().x < e-M) q.pop_front();
		if(q.empty()){
			return -1; // impossible
		}
		q.eb(e, q.front().y+1);
	}
  	return q.back().y;
}
/*
8 3 5
3 3 1 3 4 4 2 2
3 0 1 2
2 2 3
2 3 4

5 4 4
1 0 1 2 2
2 0 1
1 1
1 2
1 3
*/

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -