| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 899950 | PoPularPlusPlus | Painting Walls (APIO20_paint) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}