oj.uz

Submission #74159

# Submission time Handle Problem Language Result Execution time Memory
74159 2018-08-30T10:29:18 Z jiaqing23 Zalmoxis (BOI18_zalmoxis) C++14
95 / 100
 901 ms 81168 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];

void split(int k){
    for(int i = 0; i < 35; i++) cnt[i] = 0;
    cnt[k] = 1;
    while(need){
        if(k==1) break;
        if(cnt[k]){
            cnt[k]--;
            cnt[k-1] +=2;
            need--;
        }
        else k--;

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

int main()
{
	//ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n >> k;
	for(int i = 0; i < n; i++){
        scanf("%d",&a[i]);
        s.insert(mp(a[i],i));
       //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);
                    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);
                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--){
            if(need > 0) split(add[i][j]);
            else
                printf("%d ",add[i][j]);
        }
        printf("%d ",a[i]);
       // cout<<endl;
    }

	return 0;
}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:61: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

# Verdict Execution time Memory Grader output
1 Correct 847 ms 80632 KB Output is correct
2 Correct 868 ms 80780 KB Output is correct
3 Correct 900 ms 80984 KB Output is correct
4 Correct 873 ms 80984 KB Output is correct
5 Correct 847 ms 80984 KB Output is correct
6 Correct 883 ms 80984 KB Output is correct

Subtask #2
65.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 884 ms 80984 KB Output is correct
2 Correct 847 ms 81136 KB Output is correct
3 Incorrect 901 ms 81136 KB Unexpected end of file - int32 expected
4 Correct 876 ms 81136 KB Output is correct
5 Correct 865 ms 81136 KB Output is correct
6 Correct 896 ms 81136 KB Output is correct
7 Correct 879 ms 81136 KB Output is correct
8 Correct 882 ms 81168 KB Output is correct
9 Correct 811 ms 81168 KB Output is correct
10 Correct 438 ms 81168 KB Output is correct
11 Correct 561 ms 81168 KB Output is correct
12 Correct 115 ms 81168 KB Output is correct
13 Correct 127 ms 81168 KB Output is correct
14 Correct 111 ms 81168 KB Output is correct