oj.uz

답안 #130692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130692 2019-07-15T21:21:44 Z Vardanyan Zalmoxis (BOI18_zalmoxis) C++14
65 / 100
 1000 ms 30488 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1000*1000+5;
int A[N];
int main(){
    ios_base::sync_with_stdio(false);
    int n,k;
    cin>>n>>k;
  //  if(k!=1) assert(0);
    vector<pair<int,int> > a;
    for(int i = 1;i<=n;i++){
            cin>>A[i];
            a.push_back({A[i],1});
    }
    int qan = 0;
    while(1){
        stack<pair<int,int> > st;
        for(int i = 0;i<a.size();i++){
            if(!st.size()){
                st.push({a[i].first,i});
                continue;
            }
            st.push({a[i].first,i});
            while(st.size()>=2){
                pair<int,int> x = st.top();
                st.pop();
                pair<int,int> y = st.top();
                st.pop();
                if(x.first != y.first){
                    st.push(y);
                    st.push(x);
                    break;
                }
                st.push({x.first+1,x.second});
            }
        }
        if(st.size() == 1){
            int x = st.top().first;
            if(x == 30) break;
        }
        int mn = 1000*1000*1000+5;
        int id = 0;
        while(st.size()){
            int x = st.top().first;
            int y = st.top().second;
            if(x<mn){
                mn = x;
                id = y;
            }
            st.pop();
        }
     //   cout<<mn<<endl;
        bool f = false;
        vector<pair<int,int> > nw;
        qan++;
        for(int i = 0;i<a.size();i++){
          //  cout<<a[i]<<" ";
            nw.push_back({a[i].first,a[i].second});
            if(i == id){
              //  cout<<mn<<" ";
              //  f = true;
              nw.push_back({mn,-1});
            }
        }
        a = nw;
    }

    int dif = k-qan;
    vector<int> ans;
    for(int i = 0;i<a.size();i++){
         //   cout<<a[i].first<<" ";
        if(a[i].second == 1){
          //  cout<<a[i].first<<" ";
            ans.push_back(a[i].first);
            continue;
        }
        ans.push_back(a[i].first);
        while(dif){
            int qn = log2(dif);
            if(dif == 1) qn++;
            if(ans.back() == 1) break;
            if(ans.back()-qn<=0){
                qn = ans.back()-1;
            }
           // if(qn == 0) break;
            int x = ans.back();
            ans.pop_back();
            for(int j = 0;j<(1<<qn);j++){
            //    cout<<a[i].first-qn<<" ";
                ans.push_back(x-qn);
            }
            dif-=((1<<qn)-1);
            //a[i].first = a[i].first-qn;
        }
    }
    for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";

    cout<<endl;
    return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:18:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<a.size();i++){
                       ~^~~~~~~~~
zalmoxis.cpp:56:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0;i<a.size();i++){
                       ~^~~~~~~~~
zalmoxis.cpp:53:14: warning: unused variable 'f' [-Wunused-variable]
         bool f = false;
              ^
zalmoxis.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<a.size();i++){
                   ~^~~~~~~~~
zalmoxis.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<ans.size();i++) cout<<ans[i]<<" ";
                   ~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 24404 KB Output is correct
2 Correct 277 ms 24408 KB Output is correct
3 Correct 279 ms 24404 KB Output is correct
4 Correct 272 ms 24428 KB Output is correct
5 Correct 274 ms 24408 KB Output is correct
6 Correct 272 ms 24552 KB Output is correct

Subtask #2
35.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 698 ms 30272 KB Output is correct
2 Execution timed out 1080 ms 30344 KB Time limit exceeded
3 Execution timed out 1075 ms 30488 KB Time limit exceeded
4 Correct 829 ms 30348 KB Output is correct
5 Correct 586 ms 30352 KB Output is correct
6 Correct 463 ms 30212 KB Output is correct
7 Correct 461 ms 30416 KB Output is correct
8 Correct 706 ms 30356 KB Output is correct
9 Execution timed out 1081 ms 27036 KB Time limit exceeded
10 Execution timed out 1076 ms 11724 KB Time limit exceeded
11 Execution timed out 1077 ms 16388 KB Time limit exceeded
12 Incorrect 83 ms 6368 KB doesn't contain S as a subsequence
13 Runtime error 5 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Correct 80 ms 6368 KB Output is correct