Submission #899927

#	Time	Username	Problem	Language	Result	Execution time	Memory
899927		PoPularPlusPlus	Painting Walls (APIO20_paint)	C++17	12 / 100	57 ms	18196 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

vector<int> merge(vector<int>& a , vector<int>& b , int add , int m){
	if(a.size() == 0 || b.size() == 0)return {};
	int j = 0;
	int start = 0;
	vector<int> res;
	for(int tp = a.size()-1; tp >= 0; tp--){
		if(a[tp] + add < m){
			break;
		}
		start = tp;
	}
	while(j < b.size() && b[j] < ((a[start] + add)%m))j++;
	if(b[j] == ((a[start] + add)%m))res.pb(a[start]);
	for(int i = (start + 1)%a.size(); i != start && j < b.size(); i=((i + 1)%a.size())){
		while(j < b.size() && b[j] < ((a[i] + add)%m))j++;
		if(b[j] == ((a[i] + add)%m))res.pb(a[i]);
	}
	return res;
}

int minimumInstructions(int n , int m , int k , vector<int> final , vector<int> siz , vector<vector<int>> like){
	bool pos[n];
	memset(pos,0,sizeof pos);

	vector<int> painter[k + 1];

	for(int i = 0; i < m; i++){
		for(int j = 0; j < siz[i]; j++){
			painter[like[i][j]].pb(i);
		}
	}

	vector<int> start_points[n];

	int l = 0;
	while(l < n){
		int r = l + m-1;
		if(r > n-1)break;
		r = min(r , n-1);
		vector<int> valid;
		for(int i : painter[final[r]]){
			valid.pb(i);
		}
		start_points[r] = valid;
		for(int j = r - 1; j >= l; j--){
			vector<int> temp;
			for(int i : painter[final[j]]){
				temp.pb(i);
			}
			valid = merge(temp,valid,1,m);
			start_points[j] = valid;
		}

		if(valid.size()){
			pos[l] = 1;
		}

		if(r == n-1)break;

		vector<int> cur;

		for(int i : painter[final[r+1]]){
			cur.pb(i);
		}

		int add = m;

		for(int i = l + 1; i <= r; i++){
			if(i + m -1 >= n)break;
			add--;
			vector<int> temp;
			for(int j : painter[final[i+m-1]]){
				temp.pb(j);
			}
			cur = merge(cur,temp,i-(l+1),m);
			if(merge(start_points[i],cur,add,m).size()){
				pos[i] = 1;
			}
		}
		if(r + m < n){
			vector<int> temp;
			for(int j : painter[final[r+m]]){
				temp.pb(j);
			}
			pos[r+1] = merge(cur,temp,m-1,m).size() > 0;
			l = r + 2;
		}
		else break;
	}

	int ans = 0;
	vector<int> sp;
	for(int i = 0; i < n-(m-1); i++){
		if(pos[i] == 1){
			///cout << i << ' ';
			sp.pb(i);
		}
	}
	int r = 0;
	for(int i = 0; i < sp.size() && r < n; i++){
		if(sp[i] > r)return -1;
		if(i + 1 < sp.size() && sp[i+1] <= r)continue;
		ans++;
		r = sp[i] + m;
	}
	if(r != n)return -1;
	return ans;
}

Compilation message (stderr)

paint.cpp: In function 'std::vector<int> merge(std::vector<int>&, std::vector<int>&, int, int)':
paint.cpp:25:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  while(j < b.size() && b[j] < ((a[start] + add)%m))j++;
      |        ~~^~~~~~~~~~
paint.cpp:27:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i = (start + 1)%a.size(); i != start && j < b.size(); i=((i + 1)%a.size())){
      |                                                  ~~^~~~~~~~~~
paint.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   while(j < b.size() && b[j] < ((a[i] + add)%m))j++;
      |         ~~^~~~~~~~~~
paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:113:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |  for(int i = 0; i < sp.size() && r < n; i++){
      |                 ~~^~~~~~~~~~~
paint.cpp:115:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |   if(i + 1 < sp.size() && sp[i+1] <= r)continue;
      |      ~~~~~~^~~~~~~~~~~

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