oj.uz

Submission #73469

# Submission time Handle Problem Language Result Execution time Memory
73469 2018-08-28T09:56:45 Z yusufake Zalmoxis (BOI18_zalmoxis) C++
100 / 100
 603 ms 104492 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 467 ms 77136 KB Output is correct
2 Correct 403 ms 79196 KB Output is correct
3 Correct 502 ms 81600 KB Output is correct
4 Correct 401 ms 83564 KB Output is correct
5 Correct 517 ms 85876 KB Output is correct
6 Correct 603 ms 88424 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 89748 KB Output is correct
2 Correct 471 ms 92292 KB Output is correct
3 Correct 412 ms 93836 KB Output is correct
4 Correct 429 ms 95932 KB Output is correct
5 Correct 449 ms 97916 KB Output is correct
6 Correct 370 ms 100896 KB Output is correct
7 Correct 366 ms 102292 KB Output is correct
8 Correct 436 ms 104492 KB Output is correct
9 Correct 431 ms 104492 KB Output is correct
10 Correct 348 ms 104492 KB Output is correct
11 Correct 392 ms 104492 KB Output is correct
12 Correct 213 ms 104492 KB Output is correct
13 Correct 155 ms 104492 KB Output is correct
14 Correct 159 ms 104492 KB Output is correct