oj.uz

Submission #70004

# Submission time Handle Problem Language Result Execution time Memory
70004 2018-08-22T08:52:07 Z 3zp Zalmoxis (BOI18_zalmoxis) C++14
90 / 100
 458 ms 63828 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);
            break;
        }
        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) || S.top() < a[i+1]){
            ans.push_back(S.top());
            S.push(S.top());
            F[ans.size()-1] = 1;
            sf ++;
            RR();
        }
    }
    int 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();
    if(l > n + k){
        while(1) l++,l--;
    }
    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:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~
zalmoxis.cpp:77:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < X.size(); i++)
                        ~~^~~~~~~~~~
zalmoxis.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ANS.size(); i++)
                    ~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 14512 KB Output is correct
2 Correct 414 ms 14512 KB Output is correct
3 Correct 372 ms 14524 KB Output is correct
4 Correct 389 ms 14524 KB Output is correct
5 Correct 383 ms 14660 KB Output is correct
6 Correct 383 ms 14660 KB Output is correct

Subtask #2
60.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 14660 KB Output is correct
2 Correct 420 ms 17168 KB Output is correct
3 Correct 458 ms 18012 KB Output is correct
4 Runtime error 379 ms 55960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 402 ms 55960 KB Output is correct
6 Correct 374 ms 55960 KB Output is correct
7 Correct 366 ms 55960 KB Output is correct
8 Correct 336 ms 55960 KB Output is correct
9 Correct 324 ms 55960 KB Output is correct
10 Correct 180 ms 55960 KB Output is correct
11 Correct 261 ms 55960 KB Output is correct
12 Correct 111 ms 55960 KB Output is correct
13 Runtime error 175 ms 63828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 121 ms 63828 KB Output is correct