Submission #69989

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
69989	2018-08-22T08:04:17 Z	khohko	Zalmoxis (BOI18_zalmoxis)	C++17	40 / 100	1000 ms	263168 KB

zalmoxis

#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;
	if(x==0){pas.pb(0);return k-1;}
	if(k==1){pas.pb(x);return 0;}
	k--;
	k=splt(x-1,k);
	k++;
	splt(x-1,k);
	return k-1;
}

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=splt(v[i],k-ct+1)+ct-1,ct--;
		else pas.pb(v[i]);
	}
	for(auto x:pas){
		cout<<x<<" ";
	}

}

Compilation message

zalmoxis.cpp: In function 'int main()':
zalmoxis.cpp:60:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
zalmoxis.cpp:66: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	190 ms	28372 KB	Output is correct
2	Correct	216 ms	28372 KB	Output is correct
3	Correct	269 ms	28460 KB	Output is correct
4	Correct	249 ms	28516 KB	Output is correct
5	Correct	232 ms	28556 KB	Output is correct
6	Correct	235 ms	28556 KB	Output is correct

Subtask #2

10.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	276 ms	32896 KB	Expected EOF
2	Correct	182 ms	32896 KB	Output is correct
3	Correct	188 ms	33684 KB	Output is correct
4	Incorrect	243 ms	33684 KB	Expected EOF
5	Incorrect	183 ms	33684 KB	Expected EOF
6	Incorrect	221 ms	33684 KB	Expected EOF
7	Incorrect	210 ms	33684 KB	Expected EOF
8	Incorrect	232 ms	33684 KB	Expected EOF
9	Execution timed out	1097 ms	164916 KB	Time limit exceeded
10	Execution timed out	1033 ms	263168 KB	Time limit exceeded
11	Execution timed out	1050 ms	263168 KB	Time limit exceeded
12	Execution timed out	1038 ms	263168 KB	Time limit exceeded
13	Execution timed out	1038 ms	263168 KB	Time limit exceeded
14	Execution timed out	1024 ms	263168 KB	Time limit exceeded