Submission #1233540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233540		thelegendary08	Painting Walls (APIO20_paint)	C++17	40 / 100	1586 ms	304184 KiB

paint

#include "paint.h"
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define f0r(i,n) for(signed i = 0; i<n; i++)
#define FOR(i, k, n) for(signed i = k; i<n; i++)
#define vi vector<int>
#define vpii vector<pair<int,int>>
#define pii pair<int,int>
#define vb vector<bool>
#define mii map<int,int>
#define vvi vector<vector<int>>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<endl;
#define dout(a) cout<<a<<' '<<#a<<endl;
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl;
using namespace std;

signed minimumInstructions(
    signed n, signed m, signed k, std::vector<signed> c,
    std::vector<signed> a, std::vector<std::vector<signed>> b) {
   	map<pii, int>state;
   	vpii w;
   	vb can(n);
    vector<set<int>> f(k);
    f0r(i,m){
    	f0r(j, a[i]){
    		f[b[i][j]].insert(i);
    		// state[mp(i, b[i][j])] = -1;
    		// w.pb(mp(i, b[i][j]));
    	}
    }
    /*
    f0r(i,n){
    	for(auto u : f[c[i]]){
    		state[mp(i, u)] = -1;
    		w.pb(mp(i,u));
    	}
    }
    sort(w.begin(), w.end());
    */
    set<pii>proc;
    f0r(i, n){
    	if(can[i])continue;
    	for(auto u : f[c[i]]){
    		int d = i; int v = u;
    		if(proc.count(mp(d,v)))continue;
	    	int st = d;
	    	int cnt = 1;
	    	if(m == 1){
	    		can[d] = 1;
	    	}
	    	proc.insert(mp(d,v));
	    	
	    	while(1){
	    		d++; v++; v %= m;
	    		if(d >= n){
	    			break;
	    		}
	    		if(!f[c[d]].count(v)){
	    			break;
	    		}
	    		if(can[d])continue;
	    		proc.insert(mp(d,v));
	    		// dout2(st, d);
	    		if(st + m - 1 <= d){
	    			int offset = m-1;
	    			int nv = (v - offset) % m;
	    			if(nv < 0)nv += m;
	    			can[d-offset] = 1;
	    		}
	    	}
    	}
    	
    }
    // vout(can);
    vi cans;
    f0r(i, n){
    	if(can[i])cans.pb(i);
    }
    if(!can[0])return -1;
    if(cans.back() != n - m)return -1;
    int cur = 0;
    int cnt = 1;
    int ep = n - m;
    while(cur < ep){
    	cnt++; 
    	int lo = 0;
    	int hi = cans.size() - 1;
    	//last one less than or equal to cur + m
    	while(lo < hi){
    		int mid = lo + (hi - lo + 1) / 2;
    		if(cans[mid] <= cur + m){
    			lo = mid;
    		}
    		else{
    			hi = mid - 1;
    		}
    	}
    	if(cans[lo] == cur)return -1;
    	cur = cans[lo]; 
    }
    return cnt;
}

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