oj.uz

Submission #846427

# Submission time Handle Problem Language Result Execution time Memory
846427 2023-09-07T14:37:55 Z vjudge1 OGLEDALA (COI15_ogledala) C++11
0 / 100
 45 ms 13952 KB 
#include <bits/stdc++.h>
#define lg(a) (31 - __builtin_clz((a)))
#define endl ("\n")
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define vi vector<int>
#define st first
#define nd second
#define all(aa) aa.begin(), aa.end()
#define rall(aa) aa.rbegin(), aa.rend()
#define until(n, v) (int) (lower_bound(v.begin(), v.end(), n)-v.begin()) //# of elements < n
#define after(n, v) (int) (v.end()-upper_bound(v.begin(), v.end(), n))   //# of elements > n
#define sameas(n, v) (int) (upper_bound(v.begin(), v.end(), n) - lower_bound(v.begin(), v.end(), n)) //# of elements ==n
typedef long long ll;
const ll MOD = 1e9+7;
using namespace std;
/*

*/




void solve(){
	ll m; int n, qq; cin >> m >> n >> qq;

	vector<ll> initial(n);
	for(int i=0;i<n;i++){
		cin>>initial[i];
	}

	priority_queue<pair<ll, pair<ll, ll>>> q; // length, (l, r) range;
	for(int i=1;i<n;i++){
		q.push(mp(initial[i]-initial[i-1]-1, mp(-initial[i-1], -initial[i])));
	}
	q.push(mp(m-initial[n-1], mp(-m-1, -initial[n-1]) ) );
	q.push(mp(initial[0]-1, mp(0, -initial[0])));
	vector<int> B(qq);
	for(int i=0;i<qq;i++){
		cin>>B[i];
		// cout<<B[i]<<endl;
	}

	vector<int> ans(B[qq-1]);
	for(int i=0;i<n;i++){
		ans[i] = initial[i];
	}

	for(int i=n;i<=B[qq-1];i++){
		pair<ll, pair<ll, ll>> cur = q.top();
		ll dist = cur.st;
		ll l = -cur.nd.st;
		ll r = -cur.nd.nd;
		ll pos = (l+r)/2;
		q.pop();
		q.push(mp(pos-l-1, mp(-l, -pos)));
		q.push(mp(r-pos-1, mp(-pos, -r)));
		ans[i] = pos;
	}

	for(int i=0;i<qq;i++){
		cout<<ans[B[i]-1]<<endl;
	}

}

int main(){
	int test; 
    // cin >> test;
    test =1;
   	while (test--){
		solve();
    }
}

Compilation message

ogledala.cpp: In function 'void solve()':
ogledala.cpp:53:6: warning: unused variable 'dist' [-Wunused-variable]
   53 |   ll dist = cur.st;
      |      ^~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 13952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 7552 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -