oj.uz

Submission #70008

# Submission time Handle Problem Language Result Execution time Memory
70008 2018-08-22T08:57:13 Z 3zp Zalmoxis (BOI18_zalmoxis) C++14
90 / 100
 489 ms 63860 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])){
            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();
    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:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~
zalmoxis.cpp:74:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < X.size(); i++)
                        ~~^~~~~~~~~~
zalmoxis.cpp:77: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 353 ms 14420 KB Output is correct
2 Correct 353 ms 14452 KB Output is correct
3 Correct 380 ms 14544 KB Output is correct
4 Correct 343 ms 14604 KB Output is correct
5 Correct 351 ms 14632 KB Output is correct
6 Correct 340 ms 14632 KB Output is correct

Subtask #2
60.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 14648 KB Output is correct
2 Correct 364 ms 17168 KB Output is correct
3 Correct 363 ms 17988 KB Output is correct
4 Runtime error 435 ms 55932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 442 ms 55932 KB Output is correct
6 Correct 489 ms 55932 KB Output is correct
7 Correct 350 ms 55932 KB Output is correct
8 Correct 408 ms 55932 KB Output is correct
9 Correct 352 ms 55932 KB Output is correct
10 Correct 269 ms 55932 KB Output is correct
11 Correct 272 ms 55932 KB Output is correct
12 Correct 135 ms 55932 KB Output is correct
13 Runtime error 166 ms 63860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 128 ms 63860 KB Output is correct