oj.uz

Submission #74148

# Submission time Handle Problem Language Result Execution time Memory
74148 2018-08-30T10:03:53 Z jiaqing23 Zalmoxis (BOI18_zalmoxis) C++14
85 / 100
 897 ms 81068 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){
    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:58: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 858 ms 80888 KB Output is correct
2 Correct 897 ms 80888 KB Output is correct
3 Correct 843 ms 80888 KB Output is correct
4 Correct 825 ms 80888 KB Output is correct
5 Correct 846 ms 80888 KB Output is correct
6 Correct 878 ms 80928 KB Output is correct

Subtask #2
55.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 80928 KB Output is correct
2 Correct 859 ms 80928 KB Output is correct
3 Incorrect 868 ms 80928 KB Unexpected end of file - int32 expected
4 Correct 890 ms 80944 KB Output is correct
5 Correct 880 ms 80984 KB Output is correct
6 Correct 857 ms 80984 KB Output is correct
7 Correct 850 ms 81000 KB Output is correct
8 Correct 873 ms 81068 KB Output is correct
9 Incorrect 831 ms 81068 KB Expected EOF
10 Correct 390 ms 81068 KB Output is correct
11 Incorrect 890 ms 81068 KB Expected EOF
12 Correct 109 ms 81068 KB Output is correct
13 Correct 112 ms 81068 KB Output is correct
14 Correct 104 ms 81068 KB Output is correct