제출 #683889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683889		kym	벽 칠하기 (APIO20_paint)	C++14	63 / 100	1596 ms	22732 KiB

paint

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 100005;
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,tune=native")
int D[MAXN];
unordered_map<int,int> dp[2];
int store[MAXN];
vector<int> V[MAXN]; // contractors of this colour
bool can[MAXN];
struct node {
    int s,e,m,val;
    node *l, *r;
    node(int _s, int _e) {
        s=_s;e=_e;
        m=(s+e)/2;
        val=inf;
        if(s!=e) {
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void update(int x, int nval) {
        if(s==e) {
            val=nval;
            return;
        }
        if(x>m)r->update(x,nval);
        else l->update(x,nval);
        val=min(l->val,r->val);
    }
    int query(int x, int y) {
        if(s==x&&e==y) return val;
        if(x>m) return r->query(x,y);
        else if(y<=m) return l->query(x,y);
        else return min(l->query(x,m), r->query(m+1,y));
    }
} *seg;

int minimumInstructions(
    int n, int m, int k, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
    seg=new node(0,n);
    
    FOR(i,0,m-1) { // this contractor
        int y=A[i];
        FOR(j,0,y-1) { // V[i] -> the indices of contractors of this index.
            V[B[i][j]].pb(i);
        }

    }
    FOR(i,1,MAXN)D[i]=inf;
    D[0]=0;
    bool alt;
    FOR(i,0,n-1) {
        alt=i%2;
        dp[alt].clear();
        for(auto x:V[C[i]]) {
            // index of contractor that can paint this place
            // for continuous segment, all V values are the same
            // store longest segment of this same value
            int V=i-x;
            chmax(dp[alt][V],dp[1-alt][V]+1);
        }
        db(i);
        dbvp(dp[alt]);
        store[i]=dp[alt][i-(m-1)];
        //now check if i can cover from [i-m+1 to i]
        int st=i-m+1;
        if(st<0)continue;
        for(auto x:dp[alt]) {
            int idx=-(x.f-i); // idx of the contractor
            int len=min(x.s,idx+1);
            if(idx == m-1) {
                if(len>=m){
                    can[i]=1;
                    break;
                }
            }
            if(idx>=len)continue;
            //idx<len
            int curidx=i-len;
            db(curidx);
            if(curidx<0){
                continue;
            }
            int req=m-len;
            
            if(store[curidx]>=req){
                can[i]=1;
                break;
            }
        }
        //actually after this, the only value that matters is the largest val
    
    }
    dba(store,0,n-1);
    dba(can,0,n-1);
    seg->update(0,0);
    FOR(i,m,n) { // this is thing should be one indexed
        if(!can[i-1])continue;
        chmin(D[i], seg->query(i-m, i-1) + 1);
        seg->update(i, D[i]);
    }
    if(D[n]>=inf)return -1;
    else return D[n];


}

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:90:22: warning: iteration 100004 invokes undefined behavior [-Waggressive-loop-optimizations]
   90 |     FOR(i,1,MAXN)D[i]=inf;
      |                  ~~~~^~~~
paint.cpp:3:37: note: within this loop
    3 | #define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
......
   90 |     FOR(i,1,MAXN)D[i]=inf;
      |         ~~~~~~~~                     
paint.cpp:90:5: note: in expansion of macro 'FOR'
   90 |     FOR(i,1,MAXN)D[i]=inf;
      |     ^~~

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