oj.uz

답안 #618941

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
618941 2022-08-02T08:30:21 Z maximath_1 OGLEDALA (COI15_ogledala) C++11
100 / 100
 2093 ms 198436 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int MX = 1e5 + 5;
ll m; int n, q;
ll a[MX], b[MX];

vector<pair<ll, ll> > gt;
void split(ll len){
	gt.clear();
	if(len == 0) return;

	gt.push_back({len + 1, 0});
	gt.push_back({len, 1}); // v[2i].first = v[2i+1].first + 1 to deal with parity
	for(int i = 0; i < gt.size(); i += 2){
		ll nlen1 = gt[i].first / 2, ncnt1 = gt[i].second;
		ll nlen2 = (gt[i + 1].first - 1) / 2, ncnt2 = gt[i + 1].second;
		if((gt[i].first - 1) / 2 == nlen1) ncnt1 += gt[i].second;
		else ncnt2 += gt[i].second;
		if(gt[i + 1].first / 2 == nlen1) ncnt1 += gt[i + 1].second;
		else ncnt2 += gt[i + 1].second;
		if(!nlen1 && !nlen2) break;
		gt.push_back({nlen1, ncnt1}); gt.push_back({nlen2, ncnt2});
	}

	for(; gt.size() && gt.back().first == 0; gt.pop_back());
	ll cnt1 = 0ll;
	for(; gt.size() && gt.back().first == 1; gt.pop_back()) cnt1 += gt.back().second;
	if(cnt1) gt.push_back({1, cnt1});
}

ll find_pos(int i, ll find_len, ll find_id){
	ll offset = a[i] + 1, len = a[i + 1] - a[i] - 1;
	for(; len > find_len;){
		split((len - 1) / 2);
		ll cnt = 0ll;
		for(auto i : gt) if(i.first == find_len) cnt += i.second;
		if(cnt >= find_id){
			len = (len - 1) / 2;
		}else{
			offset += 1 + (len - 1) / 2;
			len /= 2;
			find_id -= cnt;
		}
	}

	assert(len == find_len);
	return offset + (len - 1) / 2;
}

vector<pair<pair<ll, ll>, int> > seg;

int main(){
	scanf("%lld %d %d", &m, &n, &q);
	for(int i = 1; i <= n; i ++)
		scanf("%lld", &a[i]);
	a[0] = 0; a[n + 1] = m + 1;
	for(int i = 0; i <= n; i ++){
		split(a[i + 1] - a[i] - 1);
		for(auto j : gt) if(j.first > 0 && j.second > 0)
			seg.push_back({j, i});
	}
	sort(seg.begin(), seg.end(), [&](pair<pair<ll, ll>, int> A, pair<pair<ll, ll>, int> B){
		if(A.first.first == B.first.first) return A.second < B.second;
		return A.first.first > B.first.first;
	});

	for(int i = 0; i < q; i ++)
		scanf("%lld", &b[i]);
	int idq = 0;
	for(; idq < q && b[idq] <= n; idq ++) printf("%lld\n", a[b[idq]]);
	ll offset = n + 1;
	for(auto i : seg){
		for(; idq < q && b[idq] < offset + i.first.second; idq ++)
			printf("%lld\n", find_pos(i.second, i.first.first, b[idq] - offset + 1));
		offset += i.first.second;
	}

	return 0;
}

Compilation message

ogledala.cpp: In function 'void split(long long int)':
ogledala.cpp:16:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < gt.size(); i += 2){
      |                 ~~^~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |  scanf("%lld %d %d", &m, &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ogledala.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
ogledala.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |   scanf("%lld", &b[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 34 ms 2448 KB Output is correct
4 Correct 30 ms 2596 KB Output is correct
5 Correct 52 ms 7312 KB Output is correct
6 Correct 69 ms 7356 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 640 KB Output is correct
2 Correct 24 ms 612 KB Output is correct
3 Correct 847 ms 198176 KB Output is correct
4 Correct 858 ms 198168 KB Output is correct
5 Correct 954 ms 198120 KB Output is correct
6 Correct 921 ms 198168 KB Output is correct

Subtask #3
59.0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 867 ms 99692 KB Output is correct
2 Correct 974 ms 99832 KB Output is correct
3 Correct 1437 ms 198280 KB Output is correct
4 Correct 1352 ms 198436 KB Output is correct
5 Correct 2093 ms 198248 KB Output is correct
6 Correct 2021 ms 198356 KB Output is correct