oj.uz

Submission #70011

# Submission time Handle Problem Language Result Execution time Memory
70011 2018-08-22T08:59:24 Z 3zp Zalmoxis (BOI18_zalmoxis) C++14
90 / 100
 477 ms 63840 KB 
#include<bits/stdc++.h>
using namespace std;
int a[2000009];
int F[2000009];
stack<int> S;
int sf = 0;
void RR(){
    while(S.size() > 1){
        int x = S.top(); S.pop();
        if(S.top() != x){
            S.push(x);
            return;
        }
        S.top() ++;
    }

}
vector<int> divide(int x, int mx){

    if(mx == 0) return {};
    if(mx == 1 || x == 0) {
        return {x};
    }
    if((1<<x) <= mx){
        vector<int> ans;
        for(int i = 0; i < (1<<x); i++)
            ans.push_back(0);
        return ans;
    }
    vector<int> ans1 = divide(x - 1, mx - 1),
    ans2 = divide(x - 1, mx - ans1.size());
    for(int i = 0; i < ans2.size(); i++)
        ans1.push_back(ans2[i]);
    return ans1;
}
main(){
    vector<int> ans;
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++){
        if(S.size() == 0){
            ans.push_back(a[i]);
            S.push(a[i]);
            continue;
        }
        S.push(a[i]);
        RR();
        ans.push_back(a[i]);
        while((i == n && S.size() > 1) || (i != n && S.top() < a[i+1])){
            if(S.size())ans.push_back(S.top());
            if(S.size()) S.push(S.top());
            F[ans.size()-1] = 1;
            RR();
        }
    }
    int x; if (S.size()) x = S.top();
    for(int i = x; i <= 29; i++)
        ans.push_back(i),
        F[ans.size()-1] = 1;
    vector<int> ANS;
    int l = ans.size();
    for(int i = 0; i < ans.size(); i++){
        if(F[i] == 0)
        {
            ANS.push_back(ans[i]);
            continue;
        }

        vector<int> X = divide(ans[i], n + k - l + 1);
        l += X.size() - 1;
        for(int i = 0; i < X.size(); i++)
            ANS.push_back(X[i]);
    }
    for(int i = 0; i < ANS.size(); i++)
        cout<<ANS[i] << " ";
    cout<<endl;
}

Compilation message

zalmoxis.cpp: In function 'std::vector<int> divide(int, int)':
zalmoxis.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans2.size(); i++)
                    ~~^~~~~~~~~~~~~
zalmoxis.cpp: At global scope:
zalmoxis.cpp:36:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:64:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~
zalmoxis.cpp:73:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < X.size(); i++)
                        ~~^~~~~~~~~~
zalmoxis.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ANS.size(); i++)
                    ~~^~~~~~~~~~~~
zalmoxis.cpp:58:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x; if (S.size()) x = S.top();
         ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 14428 KB Output is correct
2 Correct 477 ms 14584 KB Output is correct
3 Correct 404 ms 14584 KB Output is correct
4 Correct 387 ms 14584 KB Output is correct
5 Correct 387 ms 14596 KB Output is correct
6 Correct 381 ms 14836 KB Output is correct

Subtask #2
60.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 14836 KB Output is correct
2 Correct 398 ms 17184 KB Output is correct
3 Correct 337 ms 17988 KB Output is correct
4 Runtime error 413 ms 56048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 341 ms 56048 KB Output is correct
6 Correct 340 ms 56048 KB Output is correct
7 Correct 312 ms 56048 KB Output is correct
8 Correct 357 ms 56048 KB Output is correct
9 Correct 322 ms 56048 KB Output is correct
10 Correct 219 ms 56048 KB Output is correct
11 Correct 258 ms 56048 KB Output is correct
12 Correct 167 ms 56048 KB Output is correct
13 Runtime error 164 ms 63840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 132 ms 63840 KB Output is correct