#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,res1;
int left = 0 , right = a.size() - 1;
while(left <= right){
int mid = (left + right)/2;
if(a[mid]+add < m){
left mid + 1;
}
else {
start = mid;
right = mid - 1;
}
}
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)){
if(start == 0)res.pb(a[start]);
else res1.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)){
if(start == 0 || i < start)res.pb(a[i]);
else res1.pb(a[i]);
}
}
for(int i : res1)res.pb(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
paint.cpp: In function 'std::vector<int> merge(std::vector<int>&, std::vector<int>&, int, int)':
paint.cpp:23:8: error: expected ';' before 'mid'
23 | left mid + 1;
| ^~~~
| ;
paint.cpp:23:4: warning: statement has no effect [-Wunused-value]
23 | left mid + 1;
| ^~~~
paint.cpp:36:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while(j < b.size() && b[j] < ((a[start] + add)%m))j++;
| ~~^~~~~~~~~~
paint.cpp:41:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = (start + 1)%a.size(); i != start && j < b.size(); i=((i + 1)%a.size())){
| ~~^~~~~~~~~~
paint.cpp:42:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | 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:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
131 | for(int i = 0; i < sp.size() && r < n; i++){
| ~~^~~~~~~~~~~
paint.cpp:133:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | if(i + 1 < sp.size() && sp[i+1] <= r)continue;
| ~~~~~~^~~~~~~~~~~
