답안 #925106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925106 2024-02-10T18:59:21 Z parlimoos RLE (BOI06_rle) C++14
100 / 100
285 ms 89180 KB
//Be Name KHODA
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , m;
vector<array<ll , 2>> bls;
arr(2) lst[4];
int infs[100000][3];
int mns[2000000][2];
vector<int> o;

void addLst(int li , int i){
    if(lst[li][1] == 0) infs[i][0] = -1;
    else infs[i][0] = lst[li][0] , infs[lst[li][0]][1] = i;
    lst[li][0] = i , lst[li][1]++ , infs[i][1] = -1;
}
void delLst(int li , int i){
    if(infs[i][1] == -1) lst[li][0] = infs[i][0];
    else infs[infs[i][1]][0] = infs[i][0];
    if(infs[i][0] != -1) infs[infs[i][0]][1] = infs[i][1];
    lst[li][1]--;
}
void add(int c , ll x){
    int len = (int)bls.size();
    if(!bls.empty() and bls[len - 1][0] == c) bls[len - 1][1] += x;
    else bls.pb({c , x});
}
int clc(int i , bool sgn){
    ll ln = n;
    if(sgn) return (3 * ((bls[i][1] + ln - 1) / ln));
    int res = 3 * (bls[i][1] / (ln + 2));
    if(bls[i][1] % (ln + 2) > 2) res += 3;
    else res += bls[i][1] % (ln + 2);
    return res;
}
void clcO(int i , int sgn){
    ll ln = n;
    if(sgn == bls[i][0]){
        ll d = bls[i][1];
        while(d > 0) o.pb(min(ln , d) - 1) , o.pb(sgn) , o.pb(sgn) , d -= min(ln , d);
    }else{
        ll d = bls[i][1];
        while(d > 3) o.pb(min(ln + 2 , d) - 3) , o.pb(bls[i][0]) , o.pb(sgn) , d -= min(ln + 2 , d);
        for(int j = 0 ; j < d ; j++) o.pb(bls[i][0]);
    }
}
void f(){
    int mn = 0;
    lst[0] = {-1 , 0};
    lst[1] = lst[0] , lst[2] = lst[0] , lst[3] = lst[0];
    addLst(0 , 0);
    for(int i = 1 ; i < n ; i++) addLst(3 , i) , infs[i][2] = 3;
    int len = (int)bls.size();
    for(int i = 0 ; i < len ; i++){
        int d = clc(i , 1) - clc(i , 0);
        int inx = bls[i][0];
        if(d > 0){
            delLst(infs[inx][2] - mn , inx);
            int dd = infs[inx][2] - mn + d;
            if(dd <= 3) addLst(dd , inx);
            while(lst[0][1] == 0) mn++ , lst[0] = lst[1] , lst[1] = lst[2] , lst[2] = lst[3] , lst[3] = {-1 , 0};

            infs[inx][2] = min(d + infs[inx][2] , mn + 3);
            if(dd > 3) addLst(infs[inx][2] - mn , inx);
        }
        mns[i][0] = lst[0][0] , mns[i][1] = mn;
    }
    int e = mns[len - 1][0] , sz = mns[len - 1][1];
    for(int i = len - 1 ; i >= 0 ; i--){
        clcO(i , e);
        if(i == 0){
            if(e != 0) o.pb(0) , o.pb(e) , o.pb(0);
        }else{
            int d = 0;
            if(bls[i][0] == e) d = clc(i , 1) - clc(i , 0);
            if(mns[i - 1][1] + 3 + d == sz) o.pb(0) , o.pb(e) , o.pb(mns[i - 1][0]) , e = mns[i - 1][0] , sz = mns[i - 1][1];
            else sz -= d;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int e = 0;
    cin >> n >> m;
    for(int i = 0 ; i < m ;){
        int d;
        cin >> d;
        if(d != e) add(d , 1) , i++;
        else{
            int d1 , d2;
            cin >> d1 >> d2;
            if(d1 != e and d2 == 0) e = d1;
            else if(d1 == e) add(e , d2 + 1);
            else add(d1 , d2 + 3);
            i += 3;
        }
    }
    f();
    cout << (int)o.size() << endl;
    for(int i = (int)o.size() - 1 ; i >= 0 ; i--) cout << o[i] << " ";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 11 ms 3672 KB Output is correct
7 Correct 85 ms 13572 KB Output is correct
8 Correct 115 ms 18760 KB Output is correct
9 Correct 202 ms 42716 KB Output is correct
10 Correct 85 ms 12796 KB Output is correct
11 Correct 70 ms 14152 KB Output is correct
12 Correct 130 ms 30128 KB Output is correct
13 Correct 182 ms 25400 KB Output is correct
14 Correct 57 ms 15804 KB Output is correct
15 Correct 35 ms 10184 KB Output is correct
16 Correct 214 ms 28440 KB Output is correct
17 Correct 221 ms 32052 KB Output is correct
18 Correct 214 ms 36452 KB Output is correct
19 Correct 285 ms 89180 KB Output is correct
20 Correct 277 ms 88080 KB Output is correct