oj.uz

Submission #70006

# Submission time Handle Problem Language Result Execution time Memory
70006 2018-08-22T08:54:32 Z 3zp Zalmoxis (BOI18_zalmoxis) C++14
0 / 100
 1000 ms 63692 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 8424 KB Time limit exceeded
2 Execution timed out 1079 ms 8656 KB Time limit exceeded
3 Execution timed out 1083 ms 8656 KB Time limit exceeded
4 Execution timed out 1074 ms 8656 KB Time limit exceeded
5 Execution timed out 1084 ms 8700 KB Time limit exceeded
6 Execution timed out 1086 ms 8700 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 8712 KB Time limit exceeded
2 Execution timed out 1082 ms 10948 KB Time limit exceeded
3 Execution timed out 1082 ms 12052 KB Time limit exceeded
4 Runtime error 425 ms 55920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Execution timed out 1072 ms 55920 KB Time limit exceeded
6 Execution timed out 1074 ms 55920 KB Time limit exceeded
7 Execution timed out 1072 ms 55920 KB Time limit exceeded
8 Execution timed out 1080 ms 55920 KB Time limit exceeded
9 Execution timed out 1080 ms 55920 KB Time limit exceeded
10 Execution timed out 1069 ms 55920 KB Time limit exceeded
11 Execution timed out 1080 ms 55920 KB Time limit exceeded
12 Execution timed out 1054 ms 55920 KB Time limit exceeded
13 Runtime error 170 ms 63692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Execution timed out 1081 ms 63692 KB Time limit exceeded