oj.uz

Submission #70003

# Submission time Handle Problem Language Result Execution time Memory
70003 2018-08-22T08:50:41 Z 3zp Zalmoxis (BOI18_zalmoxis) C++14
90 / 100
 437 ms 63808 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();
    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: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++)
                    ~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 14428 KB Output is correct
2 Correct 430 ms 14428 KB Output is correct
3 Correct 437 ms 14452 KB Output is correct
4 Correct 392 ms 14860 KB Output is correct
5 Correct 351 ms 14860 KB Output is correct
6 Correct 323 ms 14860 KB Output is correct

Subtask #2
60.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 14860 KB Output is correct
2 Correct 388 ms 17240 KB Output is correct
3 Correct 347 ms 18016 KB Output is correct
4 Runtime error 435 ms 55996 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 352 ms 55996 KB Output is correct
6 Correct 419 ms 55996 KB Output is correct
7 Correct 337 ms 55996 KB Output is correct
8 Correct 376 ms 55996 KB Output is correct
9 Correct 306 ms 55996 KB Output is correct
10 Correct 190 ms 55996 KB Output is correct
11 Correct 242 ms 55996 KB Output is correct
12 Correct 100 ms 55996 KB Output is correct
13 Runtime error 138 ms 63808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 146 ms 63808 KB Output is correct