oj.uz

Submission #70002

# Submission time Handle Problem Language Result Execution time Memory
70002 2018-08-22T08:41:43 Z 3zp Zalmoxis (BOI18_zalmoxis) C++14
90 / 100
 500 ms 32480 KB 
#include<bits/stdc++.h>
using namespace std;
int a[1000009];
int F[1000009];
    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};
    }
    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:25: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:29:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:58:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~
zalmoxis.cpp:66:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < X.size(); i++)
                        ~~^~~~~~~~~~
zalmoxis.cpp:69: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 366 ms 14400 KB Output is correct
2 Correct 343 ms 14456 KB Output is correct
3 Correct 500 ms 14568 KB Output is correct
4 Correct 393 ms 14568 KB Output is correct
5 Correct 376 ms 14596 KB Output is correct
6 Correct 407 ms 14596 KB Output is correct

Subtask #2
60.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 14728 KB Output is correct
2 Correct 346 ms 17180 KB Output is correct
3 Correct 333 ms 18080 KB Output is correct
4 Runtime error 267 ms 24720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Correct 373 ms 26632 KB Output is correct
6 Correct 321 ms 26668 KB Output is correct
7 Correct 400 ms 26816 KB Output is correct
8 Correct 366 ms 26816 KB Output is correct
9 Correct 306 ms 29504 KB Output is correct
10 Correct 297 ms 29504 KB Output is correct
11 Correct 288 ms 29504 KB Output is correct
12 Correct 211 ms 29504 KB Output is correct
13 Runtime error 74 ms 32480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 262 ms 32480 KB Output is correct