oj.uz

Submission #70012

# Submission time Handle Problem Language Result Execution time Memory
70012 2018-08-22T09:01:44 Z 3zp Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 457 ms 17976 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++){
        S.push(a[i]);
        RR();
        ans.push_back(a[i]);
        while((i == n && S.size() > 1) || (i != n && S.top() < a[i+1])){
            if(S.size())ans.push_back(S.top());
            if(S.size()) S.push(S.top());
            F[ans.size()-1] = 1;
            RR();
        }
    }
    int x; if (S.size()) 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:59:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ans.size(); i++){
                    ~~^~~~~~~~~~~~
zalmoxis.cpp:68:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < X.size(); i++)
                        ~~^~~~~~~~~~
zalmoxis.cpp:71:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < ANS.size(); i++)
                    ~~^~~~~~~~~~~~
zalmoxis.cpp:53:9: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int x; if (S.size()) x = S.top();
         ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 345 ms 14432 KB Output is correct
2 Correct 331 ms 14568 KB Output is correct
3 Correct 408 ms 14640 KB Output is correct
4 Correct 342 ms 14640 KB Output is correct
5 Correct 457 ms 14640 KB Output is correct
6 Correct 387 ms 14640 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 14640 KB Output is correct
2 Correct 353 ms 17016 KB Output is correct
3 Correct 337 ms 17976 KB Output is correct
4 Correct 390 ms 17976 KB Output is correct
5 Correct 373 ms 17976 KB Output is correct
6 Correct 390 ms 17976 KB Output is correct
7 Correct 358 ms 17976 KB Output is correct
8 Correct 359 ms 17976 KB Output is correct
9 Correct 328 ms 17976 KB Output is correct
10 Correct 216 ms 17976 KB Output is correct
11 Correct 246 ms 17976 KB Output is correct
12 Correct 104 ms 17976 KB Output is correct
13 Correct 132 ms 17976 KB Output is correct
14 Correct 134 ms 17976 KB Output is correct