Submission #73469

#	Time	Username	Problem	Language	Result	Execution time	Memory
73469		yusufake	Zalmoxis (BOI18_zalmoxis)	C++98	100 / 100	603 ms	104492 KiB

zalmoxis

#include<bits/stdc++.h>
using namespace std;

#define _ int v, int tl, int tr, int l, int r
#define tm (tl+tr >> 1)
#define sol v+v,tl,tm,l,r
#define sag v+v+1,tm+1,tr,l,r

#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pp pair<int,int>

const int N = 1e6 + 6;
vector < int > V[N],U[N];
int ata[N],sz[N],H[N],A[N],B[N],n,k,i,j;

int find(int x){
    return ata[x] == x ? x : ata[x] = find(ata[x]);
}
void f(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y || A[x] != A[y]) return;
    if(x < y) swap(x,y);
    ata[y] = x;
    sz[x] += sz[y];
}
void g(int x){
    if(H[x]) return;
    H[x] = 1;
    //if(j == 26) cout << x << " " << A[x] << " " << sz[x] << " ss\n";
    if(sz[x]&1) k--, U[x].pb(A[x]);
    sz[x] = sz[x]+1 >> 1;
    V[ ++A[x] ].pb(x);
}

int main(){
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%d",&A[i]);
        B[i] = A[i];
        ata[i] = i;
        sz[i] = 1;
        V[ A[i] ].pb(i);
    }

    A[0] = A[n+1] = -1;
    for(j=0;j<30;j++){
        for(auto i : V[j])
            f(i,i+1), f(i,i-1);
        for(auto i : V[j]) H[ find(i) ] = 0;
        for(auto i : V[j]) g( find(i) );
    }

    for(i=1;i<=n;i++){
        printf("%d ",B[i]);
        for(auto t : U[i]){
            deque < int > Q;
            Q.pb(t);
            for(; k && Q.front() ; k--){
                Q.pb(Q.front()-1);
                Q.pb(Q.front()-1);
                Q.pop_front();
            }
            for(auto x : Q)
                printf("%d ", x);
        }
    }

    return 0;
}

Compilation message (stderr)

zalmoxis.cpp: In function 'void g(int)':
zalmoxis.cpp:35:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     sz[x] = sz[x]+1 >> 1;
             ~~~~~^~
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
zalmoxis.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&A[i]);
         ~~~~~^~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70