제출 #1132176

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1132176		t9unkubj	Painting Walls (APIO20_paint)	C++20	0 / 100	0 ms	328 KiB

paint

#ifdef t9unkubj
#include"debug.cpp"
//#include"template_no_debug.h"
#else 
#define dbg(...) 199958
#endif

#undef _GLIBCXX_DEBUG
#pragma GCC optimize("O3")
using namespace std;
#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
    if(x>y){
        x=y;
        return true;
    }
    return false;
}
template<class T, class F>
bool chmax(T &x, F y){
    if(x<y){
        x=y;
        return true;
    }
    return false;
}
double pass_time=0;

int solve(int n,int m,int k,vc<int>c,vc<int>a,vvc<int>b){
    vvc<int>cols(n);
    rep(i,m){
        for(auto&x:b[i]){
            cols[x].push_back(i);
        }
    }

    vc<int>ok_cnt((n+m)*2);
    vc<int>ok(n-m+1);
    int yoi=0;
    int OFFSET=n+m;
    auto F=[&](int i,int coef){
        for(auto&x:cols[c[i]]){
            if(coef==1){
            ok_cnt[(-i+x)+OFFSET]++;
            if(ok_cnt[(-i+x)+OFFSET]==m){
                yoi++;
            }
            ok_cnt[(-(i+m)+x)+OFFSET]++;
            if(ok_cnt[(-(i+m)+x)+OFFSET]==m){
                yoi++;
            }
            }else{
            if(ok_cnt[(-i+x)+OFFSET]==m){
                yoi--;
            }
            ok_cnt[(-i+x)+OFFSET]--;
            if(ok_cnt[(-(i+m)+x)+OFFSET]==m){
                yoi--;
            }
            ok_cnt[(-(i+m)+x)+OFFSET]--;
            }
        }
    };
    rep(i,m){
        F(i,1);
    }
    ok[0]=!!yoi;
    REP(i,m,n){
        F(i-m,-1);
        F(i,1);
        ok[i-m+1]=!!yoi;
    }
    if(!ok[0])return -1;
    dbg(ok);
    set<int>st;
    rep(i,n-m+1)if(ok[i])st.insert(i);
    int ans=1;
    int now=0;
    while(1){
        auto it=st.upper_bound(now+m);
        if(it==st.begin())return -1;
        it=prev(it);
        if(*it<=now)return -1;
        now=*it;
        ++ans;
        if(now==n-m)break;
    }
    return ans;
}
int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
  return solve(N,M,K,C,A,B);
}
namespace judge{
    void run(){
        int n,m,k;
        cin>>n>>m>>k;
        vc<int>c(n);
        rep(i,n)cin>>c[i];
        vc<int>a(m);
        vvc<int>b(m);
        rep(i,m){
            cin>>a[i];
            b[i].resize(a[i]);
            rep(j,a[i])cin>>b[i][j];
        }
        dbg(solve(n,m,k,c,a,b));
    }
};
//int main(){judge::run();}
//g++ paint.cpp -D t9unkubj

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