oj.uz

Submission #69994

# Submission time Handle Problem Language Result Execution time Memory
69994 2018-08-22T08:07:32 Z khohko Zalmoxis (BOI18_zalmoxis) C++17
100 / 100
 272 ms 34956 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define MAX ((ll)(1e12+100))
#define MX ((ll)(1e6+100))
#define ARRS ((ll)(2e6+100))
#define HS ((ll)(233))
#define MOD ((ll)(1e9+7))
#define EP ((double)(1e-9))
#define LG 21
#define mul(a,b) a=((a)*(b))%MOD
using namespace std;
ll a[ARRS];
ll f[ARRS];
ll n;
vector<ll> v;

ll go(ll x,ll i){
	if(x==a[i]){v.pb(x);return i+1;}
	//if(x>a[i]){
	i=go(x-1,i);
	if(x<=a[i]||i==n){
		f[v.size()]=1;
		v.pb(x-1);
	}
	else
		i=go(x-1,i);
	return i;
	//}
}
vector<ll> pas;
ll splt(ll x,ll k){
	//cout<<x<<" "<<k<<endl;
	ll sk=k;
	if(x==0){pas.pb(0);return 1;}
	if(k==1){pas.pb(x);return 1;}
	k-=splt(x-1,k-1);
	k-=splt(x-1,k);
	return sk-k;
}

int main(){
	#ifdef KHOKHO
		freopen("in.in","r",stdin);
		freopen("out.out","w",stdout);
	#endif // KHOKHO
	ios::sync_with_stdio(0);
	ll k;
	cin>>n>>k;
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	go(30,0);
	ll ct=0;
	for(int i=0; i<v.size(); i++){
		//cout<<v[i]<<" "<<f[i]<<endl;
		ct+=f[i];
	}
	//k-=v.size()-n;
//	vector<ll> pas;
	for(int i=0; i<v.size(); i++){
		if(f[i])
			k=k-splt(v[i],k-ct+1),ct--;
		else pas.pb(v[i]);
	}
	for(auto x:pas){
		cout<<x<<" ";
	}

}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
zalmoxis.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 29396 KB Output is correct
2 Correct 202 ms 29472 KB Output is correct
3 Correct 233 ms 29532 KB Output is correct
4 Correct 222 ms 29568 KB Output is correct
5 Correct 226 ms 29576 KB Output is correct
6 Correct 249 ms 29576 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 29640 KB Output is correct
2 Correct 238 ms 32948 KB Output is correct
3 Correct 211 ms 34704 KB Output is correct
4 Correct 272 ms 34704 KB Output is correct
5 Correct 229 ms 34704 KB Output is correct
6 Correct 234 ms 34704 KB Output is correct
7 Correct 218 ms 34704 KB Output is correct
8 Correct 240 ms 34704 KB Output is correct
9 Correct 258 ms 34956 KB Output is correct
10 Correct 152 ms 34956 KB Output is correct
11 Correct 169 ms 34956 KB Output is correct
12 Correct 112 ms 34956 KB Output is correct
13 Correct 101 ms 34956 KB Output is correct
14 Correct 88 ms 34956 KB Output is correct