oj.uz

답안 #67878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
67878 2018-08-15T11:37:32 Z yusufake Permutation Recovery (info1cup17_permutation) C++
43 / 100
 4000 ms 41932 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; 
typedef vector < int > vi;

vector < int > s[N],A[N];
int pri[N],sz[N],lz[N],L[N],R[N],ans[N],uu;
char u[N+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]);
}



vi top(vi a, vi b){
    if(a.size() < b.size()) swap(a,b);
    int t,i,j,h=0;
    for(i=a.size()-1,j=b.size()-1 ; i>=0 ; i--,j--){
        t = a[i]+h+(j<b.size() ? b[j] : 0);
        if(t >= 10) { h=1; t-=10; }
        else h=0;
        a[i] = t;
    }
    if(h) a.insert(a.begin() , 1);
    return a;
}
vi cik(vi a, vi b){
    int t,i,j,h=0;
    for(i=a.size()-1,j=b.size()-1 ; i >= 0; i--,j--){
        t = a[i]-h-(j<b.size() ? b[j] : 0);
        if(t < 0) { h=1; t+=10; }
        else h=0;
        a[i] = t;
    }
    for(; a.size()>1 && a[0] == 0 ;) a.erase(a.begin());
    return a;
}

void relax(int x){ 
    sz[x] = sz[ L[x] ] + sz[ R[x] ] + 1; 
    s[x] = top(A[x] , top(s[ L[x] ] , s[ R[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;
    }
}

bool g(vi &a, vi &b){
    if(a.size() < b.size()) return 1;
    if(a.size() > b.size()) return 0;
    for(int i=0; i<a.size(); i++){
        if(b[i] > a[i])
            return 1;
        if(a[i] > b[i])
            return 0;
    }
    return 1; 
}

void split(int x, vector <int> k, int &a, int &b){
    if(x == 0){
        a = b = 0;
        return;
    }
    push(x);
    if(g(k,s[ L[x] ])){
        split(L[x], k, a, b);
        L[x] = b;
        b = x;
    }
    else{
        vi vv = cik(k,s[ L[x] ]);
        vv = cik(vv,A[x]);
        split(R[x], vv, 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);
}    

vi bir,x,y,t; 
int n,i,j,a,b,root;
int main(){
    bir.pb(1);
    s[0].pb(0);
    A[0].pb(0);
    y.pb(0);
    scanf("%lld",&n);
    
    srand(time(NULL));
    for(i=1;i<=n;i++){
        scanf(" %s", u);
        uu = strlen(u);
        x.clear();
        for(j=0;j<uu;j++) x.pb(u[j]-'0');
        t = cik(x,y);
        t = cik(t,bir);
        split(root, t, a, b);
        t = cik(x,y);
        sz[i] = 1;
        pri[i] = rand();
        s[i] = A[i] = t;
        root = mrg( mrg(a,i) , b );
        y = x;
    }
    
    f(root,0);
    for(i=1;i<=n;i++) printf("%lld ",ans[i]);
    return 0;
}

Compilation message

permutation.cpp: In function 'vi top(vi, vi)':
permutation.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         t = a[i]+h+(j<b.size() ? b[j] : 0);
                     ~^~~~~~~~~
permutation.cpp: In function 'vi cik(vi, vi)':
permutation.cpp:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         t = a[i]-h-(j<b.size() ? b[j] : 0);
                     ~^~~~~~~~~
permutation.cpp: In function 'bool g(vi&, vi&)':
permutation.cpp:76:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++){
                  ~^~~~~~~~~
permutation.cpp: In function 'int main()':
permutation.cpp:120:20: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
     scanf("%lld",&n);
                  ~~^
permutation.cpp:140:44: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int' [-Wformat=]
     for(i=1;i<=n;i++) printf("%lld ",ans[i]);
                                      ~~~~~~^
permutation.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
permutation.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", u);
         ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 15 ms 9832 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 15 ms 9832 KB Output is correct
3 Correct 33 ms 10292 KB Output is correct
4 Correct 41 ms 10352 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 15 ms 9832 KB Output is correct
3 Correct 33 ms 10292 KB Output is correct
4 Correct 41 ms 10352 KB Output is correct
5 Execution timed out 4027 ms 41932 KB Time limit exceeded

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 15 ms 9832 KB Output is correct
3 Correct 33 ms 10292 KB Output is correct
4 Correct 41 ms 10352 KB Output is correct
5 Execution timed out 4027 ms 41932 KB Time limit exceeded

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 15 ms 9832 KB Output is correct
3 Correct 33 ms 10292 KB Output is correct
4 Correct 41 ms 10352 KB Output is correct
5 Execution timed out 4027 ms 41932 KB Time limit exceeded

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 15 ms 9832 KB Output is correct
3 Correct 33 ms 10292 KB Output is correct
4 Correct 41 ms 10352 KB Output is correct
5 Execution timed out 4027 ms 41932 KB Time limit exceeded

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 9720 KB Output is correct
2 Correct 15 ms 9832 KB Output is correct
3 Correct 33 ms 10292 KB Output is correct
4 Correct 41 ms 10352 KB Output is correct
5 Execution timed out 4027 ms 41932 KB Time limit exceeded