Submission #650671

#	Time	Username	Problem	Language	Result	Execution time	Memory
650671		ymm	Painting Walls (APIO20_paint)	C++17	100 / 100	398 ms	31660 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100010;
vector<int> col2con[N];
set<int> con2col[N];
int res[N];
int lst_nonmatch[N];
int interval_match[N];
int cnt_seg, cnt_con, cnt_col;

int find_nonmatch(int seg, int con)
{
	int mod = (con - seg) % cnt_con;
	mod = mod < 0? mod + cnt_con: mod;
	if (lst_nonmatch[mod] >= seg)
		return lst_nonmatch[mod];
	Loop (i,seg,cnt_seg) {
		if (!con2col[(con+i-seg)%cnt_con].count(res[i])) {
			lst_nonmatch[mod] = i;
			return i;
		}
	}
	lst_nonmatch[mod] = cnt_seg;
	return cnt_seg;
}

int minimumInstructions(int cnt_seg, int cnt_con, int cnt_col,
                        vector<int> res, vector<int> cnt_like,
                        vector<vector<int>> likes) {
	::cnt_seg = cnt_seg;
	::cnt_con = cnt_con;
	::cnt_col = cnt_col;
	Loop (i,0,cnt_seg)
		::res[i] = res[i];
	Loop (i,0,cnt_con) {
		Loop (j,0,cnt_like[i]) {
			col2con[likes[i][j]].push_back(i);
			con2col[i].insert(likes[i][j]);
		}
	}
	memset(lst_nonmatch, -1, sizeof(lst_nonmatch));
	int lst_cover = 0;
	Loop (seg,0,cnt_seg-cnt_con+1) {
		for (int con : col2con[res[seg]]) {
			if (find_nonmatch(seg, con) >= seg + cnt_con) {
				lst_cover = seg + cnt_con;
				interval_match[seg] = 1;
				break;
			}
		}
		if (seg == lst_cover)
			return -1;
	}
	if (!interval_match[cnt_seg-cnt_con])
		return -1;
	set<int> bag;
	lst_cover = 0;
	int ans = 0;
	Loop (i,0,cnt_seg-cnt_con+1) {
		if (interval_match[i])
			bag.insert(i + cnt_con);
		if (i == lst_cover) {
			++ans;
			lst_cover = *bag.rbegin();
		}
		assert(i < lst_cover);
	}
	if (lst_cover < cnt_seg) {
		lst_cover = *bag.rbegin();
		++ans;
	}
	assert(lst_cover == cnt_seg);
	return ans;
}

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