Submission #846244

#	Time	Username	Problem	Language	Result	Execution time	Memory
846244		vjudge1	OGLEDALA (COI15_ogledala)	C++17	0 / 100	312 ms	524288 KiB

ogledala

#include<bits/stdc++.h>
#define int long long
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int32_t main(){
	int m,n,q;
	cin>>m>>n>>q;
	set<pair<int,int>>s;
	int a[n];
	for(int i=0;i<n;i++)cin>>a[i];
	int b[q];
	for(int i=0;i<q;i++)cin>>b[i];
	s.insert({1,m});
	int ans[n+m];
	for(int i=0;i<n;i++){
		auto ind=s.upper_bound({a[i],0LL});
		ind=prev(ind);
		pair<int,int>p=*ind;
		s.erase(ind);
		if(a[i]!=p.ff){
			s.insert({p.ff,a[i]-p.ff});
		}
		if(a[i]!=p.ff+p.ss-1){
			s.insert({a[i]+1,p.ss-(a[i]-p.ff+1)});
		}
		ans[i]=a[i];
	}
	set<pair<int,int>>s2;
	for(auto i:s)s2.insert({-i.ss,i.ff});
	for(int i=n;i<m;i++){
		pair<int,int>p=*s2.begin();
		s2.erase(s2.begin());
		p.ff=-p.ff;
		int ind=p.ss+(p.ff-1)/2;
		ans[i]=ind;
		if(ind!=p.ss){
			s2.insert({-(ind-p.ss),p.ss});
		}
		if(ind!=p.ss+p.ff-1){
			s2.insert({-(p.ff-(ind-p.ss+1)),ind+1});
		}
	}
	for(int i=0;i<q;i++){
		cout<<ans[b[i]-1]<<endl;
	}
}

• Subtask 1: 0 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59