oj.uz

Submission #27502

# Submission time Handle Problem Language Result Execution time Memory
27502 2017-07-13T08:18:16 Z 시제연(#1156) OGLEDALA (COI15_ogledala) C++11
41 / 100
 4000 ms 91572 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

struct lin {
	ll len; int idx; ll num;
	lin(ll l, int i, ll n):len(l),idx(i),num(n){}
	bool operator < (const lin &A) const {
		return len!=A.len?len<A.len:idx>A.idx;
	}
	bool operator == (const lin &A) const {
		return len==A.len&&idx==A.idx;
	}
};
void operator += (lin &A, const lin &B) {
	A.num += B.num;
}

auto hf = [](const pll &A) {return A.first^A.second;};
unordered_map<pll,ll,decltype(hf)> gt(10,hf);

ll g(ll n, ll k) {
	if (gt.find(pll(n,k))!=gt.end()) return gt[pll(n,k)];
	if (n<=k) return (n==k);
	return (gt[pll(n,k)] = g(n-1-n/2,k)+g(n/2,k));
}

ll f(ll n, ll k, ll t) {
	if (n==k) return (n-1)/2;
	ll v = g(n-1-n/2,k);
	return (v>=t?f(n-1-n/2,k,t):(n+1)/2+f(n/2,k,t-v));
}

ll m, n, q;
ll a[100100];

priority_queue<lin> pq;
vector<ll> que;

int main() {
	int i;

	//freopen("output","w",stdout);

	scanf("%lld%lld%lld",&m,&n,&q);
	for (i=1;i<=n;i++) {
		//a[i] = (rand()*(1LL<<31)+rand())%m;
		scanf("%lld",&a[i]); a[i]--;
	}
	sort(a+1,a+n+1);
	a[0] = -1; a[n+1] = m;
	for (i=1;i<=n+1;i++) {
		if (a[i]-a[i-1]==1) continue;
		pq.push(lin(a[i]-a[i-1]-1,i,1));
	}
	for (i=0;i<q;i++) {
		ll v;
		//v = (rand()*(1LL<<31)+rand())%m+1;
		scanf("%lld",&v);
		if (v<=n) printf("%lld\n",a[v]+1);
		else que.push_back(v);
	}

	sort(que.begin(),que.end()); //

	ll cnt = n; int p = 0;
	while(!pq.empty()) {
		lin tmp = pq.top();
		pq.pop();
		while(!pq.empty()&&pq.top()==tmp) {
			tmp += pq.top();
			pq.pop();
		}
		while(p<que.size()&&que[p]<=cnt+tmp.num) {
			printf("%lld\n",f(a[tmp.idx]-a[tmp.idx-1]-1,tmp.len,que[p]-cnt)+a[tmp.idx-1]+2); p++;
		}
		if (p==que.size()) break;
		pq.push(lin(tmp.len-1-tmp.len/2,tmp.idx,tmp.num));
		pq.push(lin(tmp.len/2,tmp.idx,tmp.num));
		cnt += tmp.num;
	}

    return 0;
}

Compilation message

ogledala.cpp: In function 'int main()':
ogledala.cpp:77:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p<que.size()&&que[p]<=cnt+tmp.num) {
          ^
ogledala.cpp:80:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (p==que.size()) break;
        ^
ogledala.cpp:48:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&m,&n,&q);
                                ^
ogledala.cpp:51:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]); a[i]--;
                      ^
ogledala.cpp:62:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&v);
                   ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2812 KB Output is correct
2 Correct 0 ms 2812 KB Output is correct
3 Correct 46 ms 5208 KB Output is correct
4 Correct 36 ms 5208 KB Output is correct
5 Correct 123 ms 14164 KB Output is correct
6 Correct 113 ms 14164 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3496 KB Output is correct
2 Correct 9 ms 3628 KB Output is correct
3 Correct 473 ms 13140 KB Output is correct
4 Correct 133 ms 13140 KB Output is correct
5 Correct 499 ms 14164 KB Output is correct
6 Correct 173 ms 14164 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 3863 ms 36268 KB Output is correct
2 Correct 3393 ms 34552 KB Output is correct
3 Execution timed out 4000 ms 91572 KB Execution timed out
4 Halted 0 ms 0 KB -