oj.uz

Submission #67794

# Submission time Handle Problem Language Result Execution time Memory
67794 2018-08-15T10:00:42 Z yusufake Permutation Recovery (info1cup17_permutation) C++
10 / 100
 3 ms 484 KB 
#include<bits/stdc++.h> 
using namespace std; 

#define pb push_back
typedef long long ll; 
typedef pair < int , int > pp; 
const int mod = 1e9 + 7; 
const int N   = 2e5 + 5; 

int pri[N],sz[N],s[N],lz[N],L[N],R[N],A[N],ans[N];

void put(int x){
    if(!x) return;
    lz[x] = 1 - lz[x];
    swap(L[x],R[x]);
}
void push(int x){
    if(!lz[x]) return;
    lz[x] = 0;
    put(L[x]); put(R[x]);
}
void relax(int x){ 
    sz[x] = sz[ L[x] ] + sz[ R[x] ] + 1; 
    s[x] = s[ L[x] ] + s[ R[x] ] + A[x];    
}
int mrg(int x, int y){
    if(!x) return y;
    if(!y) return x;
    if(pri[x] < pri[y]){
        push(y);
        L[y] = mrg(x,L[y]);
        relax(y);
        return y;
    }
    else{
        push(x);
        R[x] = mrg(R[x],y);
        relax(x);
        return x;
    }
}

void split(int x, int k, int &a, int &b){
    if(x == 0){
        a = b = 0;
        return;
    }
    push(x);
    if(k <= s[ L[x] ]){
        split(L[x], k, a, b);
        L[x] = b;
        b = x;
    }
    else{
        split(R[x], k-sz[ L[x] ]-1, a, b);
        R[x] = a;
        a = x;
    }
    relax(x);    
}    


void f(int x, int h){
    if(x==0) return;
    push(x);
    f(L[x],h); ans[x] = h+sz[ L[x] ]+1; f(R[x],h+sz[ L[x] ]+1);
}    

int main(){
    int n,i,x,y=0,a,b,t;
    scanf("%d",&n);
    int root = 0;
    srand(time(NULL));
    for(i=1;i<=n;i++){
        scanf("%lld",&x);
        t = x-y-1;
        split(root, t, a, b);
        sz[i] = 1;
        pri[i] = rand();
        s[i] = A[i] = t+1;
        root = mrg( mrg(a,i) , b );
        y = x;
    }
    
    f(root,0);
    for(i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}

Compilation message

permutation.cpp: In function 'int main()':
permutation.cpp:75:24: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
         scanf("%lld",&x);
                      ~~^
permutation.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
permutation.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&x);
         ~~~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 484 KB Output isn't correct