oj.uz

답안 #74199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
74199 2018-08-30T12:38:19 Z jiaqing23 Zalmoxis (BOI18_zalmoxis) C++14
100 / 100
 924 ms 81000 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> pi;
typedef vector<ll> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;
typedef pair<int,pair<int,int> > tri;

int n, k;
int a[1000050];
set<pi> s;
//set<int> pos;
multiset<int> s2;
vector<int> add[1000050];
int addnum = 0;
int need;
int cnt[35];
int nxt[1000050];

int tem = 0;

void split(int k1){
    assert(k1>=0);
    for(int i = 0; i < 35; i++) cnt[i] = 0;
    cnt[k1] = 1;
    //cout<<"SPLIT "<<k1<<endl;
    int j = 0;
    while(need){
        //if(need>-10 && need < 10000)cout<<"NEED : "<<need<<endl;
        if(k1==0) break;
        if(cnt[k1]>0){

            cnt[k1]--;
            cnt[k1-1] +=2;
            need --;
        }
        else k1--;

    }
    for(int i = 0; i <= 30; i++){
        for(int j = 0; j < cnt[i]; j++){
            cout << i << ' ';
            //tem++;
        }
    }
}

int main()
{
	//ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen("8z.in","r",stdin);

	cin >> n >> k;
	for(int i = 0; i < n; i++){
        scanf("%d",&a[i]);
        s.insert(mp(a[i],i));
        //assert(a[i] == 0);
       //pos.insert(i);
        if(i!=n-1) nxt[i] = i+1;
        else nxt[i] = -1;
	}

	while(1){
        auto it = s.begin();
        pi p = *it;
        //cout<<p.fi<<endl;
        if(s.size()==1){
            if(p.fi==30) break;
            else{
                for(int i = p.fi; i <= 29; i++){
                    add[p.se].pb(i);
                    //assert(i>0);
                    addnum++;
                }
                s.erase(it);
                s.insert(mp(30,p.se));
            }
        }
        else{
            auto it2 = ++it;
            pi next = *it2;
            it--;
            if(p.fi == next.fi && nxt[p.se] == next.se){
                s.erase(it2);
              //  pos.erase(next.se);
                nxt[p.se] = nxt[next.se];
                s.erase(it);
                s.insert(mp(p.fi+1, p.se));
            }
            else{
                add[p.se].pb(p.fi);
                //cout<<p.fi<<endl;
                //assert(p.fi>0);
                addnum ++;
                s.erase(it);
                s.insert(mp(p.fi+1, p.se));
            }
        }


	}

    need = k - addnum;
    for(int i = 0; i < n; i++){
        for(int j = add[i].size()-1; j >= 0; j--){
            assert(add[i][j] >= 0);
            if(need > 0) split(add[i][j]);
            else{
                printf("%d ",add[i][j]);
                //tem ++;
            }
        }
        printf("%d ",a[i]);
        //tem++;
        //cout<<"I: "<< i << endl;
    }
    //cout<<tem;
	return 0;
}

Compilation message

zalmoxis.cpp: In function 'void split(int)':
zalmoxis.cpp:42:9: warning: unused variable 'j' [-Wunused-variable]
     int j = 0;
         ^
zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
         ~~~~~^~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 872 ms 80888 KB Output is correct
2 Correct 877 ms 80908 KB Output is correct
3 Correct 893 ms 80908 KB Output is correct
4 Correct 891 ms 81000 KB Output is correct
5 Correct 858 ms 81000 KB Output is correct
6 Correct 865 ms 81000 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 894 ms 81000 KB Output is correct
2 Correct 871 ms 81000 KB Output is correct
3 Correct 924 ms 81000 KB Output is correct
4 Correct 919 ms 81000 KB Output is correct
5 Correct 864 ms 81000 KB Output is correct
6 Correct 904 ms 81000 KB Output is correct
7 Correct 900 ms 81000 KB Output is correct
8 Correct 875 ms 81000 KB Output is correct
9 Correct 789 ms 81000 KB Output is correct
10 Correct 391 ms 81000 KB Output is correct
11 Correct 606 ms 81000 KB Output is correct
12 Correct 115 ms 81000 KB Output is correct
13 Correct 119 ms 81000 KB Output is correct
14 Correct 110 ms 81000 KB Output is correct