제출 #735498

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
735498		Nahian9696	벽 칠하기 (APIO20_paint)	C++17	63 / 100	1582 ms	205736 KiB

paint

#include "paint.h"

#include <iostream>
#include <iomanip>
#include <chrono>

#include <cmath>
#include <cstring>
#include <algorithm>


#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <utility>
#include <string>
#include <vector>
#include <bitset>



using std::min;
using std::max;
using std::sort;
using std::swap;
using std::fixed;
using std::to_string;
using std::make_pair;
using std::upper_bound;
using std::lower_bound;
using std::setprecision;

using std::cin;
using std::cout;

using std::set;
using std::map;
using std::list;
using std::pair;
using std::less;
using std::tuple;
using std::stack;
using std::queue;
using std::deque;
using std::string;
using std::vector;
using std::bitset;
using std::greater;
using std::priority_queue;





typedef long double                         ld;
typedef unsigned                            ui;
typedef long long                           lli;
typedef unsigned long long                  ulli;
typedef vector<int32_t>                     vi;
typedef vector<ld>                          vld;
typedef vector<ui>                          vui;
typedef vector<lli>                         vlli;
typedef vector<ulli>                        vulli;
typedef list<int32_t>                       lsi;
typedef list<ld>                            lsld;
typedef list<ui>                            lsui;
typedef list<lli>                           lslli;
typedef list<ulli>                          lsulli;
typedef set<int32_t>                        si;
typedef set<ld>                             sld;
typedef set<ui>                             sui;
typedef set<lli>                            slli;
typedef set<ulli>                           sulli;

typedef pair<int32_t, int32_t>              pii;
typedef pair<lli, lli>                      pll;



// #define int                                 int64_t

#define endl                                "\n"
#define inp(n)                              int n; cin >> n
#define Inp(n)                              lli n; cin >> n
#define inpstr(s)                           string s; cin >> s
#define inp2(a,b)                           int a,b; cin >> a >> b
#define Inp2(a,b)                           lli a,b; cin >> a >> b
#define inparr(arr,n)                       int arr[n]; f0(t_ind, n) cin >> arr[t_ind]
#define Inparr(arr,n)                       lli arr[n]; f0(t_ind, n) cin >> arr[t_ind]

#define f0(i,n)                             for(int32_t i = 0; i <  (n); i++)
#define f1(i,n)                             for(int32_t i = 1; i <= (n); i++)
#define rep0(i,l,r)                         for(int32_t i=(l); i <  (r); i++)
#define rep1(i,l,r)                         for(int32_t i=(l); i <= (r); i++)

#define testIn                              cin >> test
#define tests                               for(int32_t testNo=1; testNo <= (test); testNo++)

#define all(x)                              (x).begin(), (x).end()
#define rall(x)                             (x).rbegin(), (x).rend()
#define asrt(v)                             sort(all(v))
#define dsrt(v)                             sort(rall(v))
#define revStr(str)                         string(rall(str))
#define len(a)                              ((int64_t)(a).size())
#define front_zero(n)                       __builtin_clzll(n)
#define back_zero(n)                        __builtin_ctzll(n)
#define total_one(n)                        __builtin_popcountll(n)
#define lcm(a, b)                           (((a)*(b))/gcd(a,b))
#define mem(a, b)                           memset(a, b, sizeof(a))

#define pb                                  push_back
#define pf                                  push_front
#define mp                                  make_pair
#define ff                                  first
#define ss                                  second

#define yes                                 cout << "yes" << endl
#define no                                  cout << "no" << endl
#define Yes                                 cout << "Yes" << endl
#define No                                  cout << "No" << endl
#define YES                                 cout << "YES" << endl
#define NO                                  cout << "NO" << endl
#define finish                              return 0
#define clean                               fflush(stdout)

#define Inf                                 (int32_t)(1e9)
#define INF                                 (lli)(1e18)
#define Eps                                 (ld)(1e-9)
#define EPS                                 (ld)(1e-18)
#define PI                                  (ld)(3.141592653589793238462643383279502884197169L)
#define MOD                                 (int32_t)(1e9+7)
#define MXN                                 (int32_t)(1e5+7)
#define antihash                            likedby

int likedby[100005];
int likedby2[100005];

bool likes[100005][2005];
vi hash;


int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {

    bool valid[N] = {0};    
    int lstvalid[N];
    int cur = -1, ans = 0;
    bool sbtsk1 = true;
    f0(i, 100005) f0(j, 2005) likes[i][j] = 0;


    f0(i, 100005) likedby[i] = -1, likedby2[i] = 0;
    f0(i, M) {
        f0(j, A[i]) {
            likedby[B[i][j]] = i;
            likedby2[B[i][j]]++;
            if(likedby2[B[i][j]] == 2) sbtsk1 = false;
        }
    }


    if(sbtsk1){f0(i, N) {
            if(likedby[C[i]] == -1) return -1;
            if(i % M != 0) {
                int df = likedby[C[i]] - likedby[C[i-1]];
                df %= M;
                df += M;
                df %= M;
                if(df != 1) {
                    return -1;
                }
            }
        }
    
        // cur = 0;
        // while(cur < N) {
        //     if(lstvalid[cur] == -1) return -1;
        //     if(lstvalid[cur] < cur - M + 1) return -1;
        //     ans++;
        //     cur = lstvalid[cur] + M;
        // }
        if(N % M == 0) {
            return N/M;
        }
        int i = N/M;
        i *= M;
        int df = likedby[C[i]] - likedby[C[i-1]];
        df %= M;
        df += M;
        df %= M;
        if(df != 1) {
            return -1;
        }
    
        return (int)((N+M-1)/M);}


    f0(i, 100005) antihash[i] = -1;
    si s;
    int nn = 0;
    f0(i, N) {
        s.insert(C[i]);
        if(len(s) > nn) {
            hash.pb(C[i]);
            antihash[C[i]] = nn;
            nn++;
        }
    }

    f0(i, M) {
        f0(j, A[i]) {
            if(antihash[B[i][j]] != -1) {
                likes[antihash[B[i][j]]][i] = true;
            }
        }
    }


    // vector<si> B(M);
    // f0(i, M) {
    //     for(int c: bbb[i]) B[i].insert(c);
    // }
    
    // bool valid[N] = {0};    
    // int lstvalid[N];

    f0(st, M) {
        int lstbreak = -1;
        f0(i, N) {
            // int color = C[i];

            if(!likes[antihash[C[i]]][(st+i)%M]) {
                lstbreak = i;
            }

            // auto it = lower_bound(B[(st+i)%M].begin(), B[(st+i)%M].end(), C[i]);
            // if (it == B[(st+i)%M].end()) {
            //     lstbreak = i;
            // } else if ((*it) != C[i]) {
            //     lstbreak = i;
            // }
            if(i - lstbreak >= M) {
                valid[i - M + 1] = true;
            }
        }
    }


    cur = -1, ans = 0;

    f0(i, N) {
        if(valid[i]) {
            cur = i;
        }
        lstvalid[i] = cur;
    }

    cur = 0;
    while(cur < N) {
        if(lstvalid[cur] == -1) return -1;
        if(lstvalid[cur] < cur - M + 1) return -1;
        ans++;
        cur = lstvalid[cur] + M;
    }

    return ans;

    return 0;
}

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