Submission #27499

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
27499	2017-07-13T08:09:36 Z	시제연(#1156)	OGLEDALA (COI15_ogledala)	C++	Compilation error	0 ms	0 KB

ogledala

#include <bits/stdc++.h>

using namespace std;

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

struct lin {
	ll len, num;
	int idx;
	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;
}

namespace std {
	template<>
	struct hash<pll> {
		size_t operator () (const pll &A) const {return hash<ll>()(A.first)^(hash<ll>()(A.second)<<1);}
	};
};

unordered_map<pll,ll> gt;

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 constructor 'lin::lin(ll, int, ll)':
ogledala.cpp:10:6: warning: 'lin::idx' will be initialized after [-Wreorder]
  int idx;
      ^
ogledala.cpp:9:10: warning:   'll lin::num' [-Wreorder]
  ll len, num;
          ^
ogledala.cpp:11:2: warning:   when initialized here [-Wreorder]
  lin(ll l, int i, ll n):len(l),idx(i),num(n){}
  ^
ogledala.cpp: At global scope:
ogledala.cpp:25:9: error: 'hash' is not a class template
  struct hash<pll> {
         ^
ogledala.cpp:25:19: error: explicit specialization of non-template 'std::hash'
  struct hash<pll> {
                   ^
ogledala.cpp: In member function 'std::size_t std::hash::operator()(const pll&) const':
ogledala.cpp:26:51: error: 'std::hash' is not a template
   size_t operator () (const pll &A) const {return hash<ll>()(A.first)^(hash<ll>()(A.second)<<1);}
                                                   ^
ogledala.cpp:26:69: error: no match for call to '(std::hash) (const long long int&)'
   size_t operator () (const pll &A) const {return hash<ll>()(A.first)^(hash<ll>()(A.second)<<1);}
                                                                     ^
ogledala.cpp:26:10: note: candidate: std::size_t std::hash::operator()(const pll&) const
   size_t operator () (const pll &A) const {return hash<ll>()(A.first)^(hash<ll>()(A.second)<<1);}
          ^
ogledala.cpp:26:10: note:   no known conversion for argument 1 from 'const long long int' to 'const pll& {aka const std::pair<long long int, long long int>&}'
ogledala.cpp:26:72: error: 'std::hash' is not a template
   size_t operator () (const pll &A) const {return hash<ll>()(A.first)^(hash<ll>()(A.second)<<1);}
                                                                        ^
ogledala.cpp:26:91: error: no match for call to '(std::hash) (const long long int&)'
   size_t operator () (const pll &A) const {return hash<ll>()(A.first)^(hash<ll>()(A.second)<<1);}
                                                                                           ^
ogledala.cpp:26:10: note: candidate: std::size_t std::hash::operator()(const pll&) const
   size_t operator () (const pll &A) const {return hash<ll>()(A.first)^(hash<ll>()(A.second)<<1);}
          ^
ogledala.cpp:26:10: note:   no known conversion for argument 1 from 'const long long int' to 'const pll& {aka const std::pair<long long int, long long int>&}'
ogledala.cpp: At global scope:
ogledala.cpp:30:1: error: 'unordered_map' does not name a type
 unordered_map<pll,ll> gt;
 ^
ogledala.cpp: In function 'll g(ll, ll)':
ogledala.cpp:33:6: error: 'gt' was not declared in this scope
  if (gt.find(pll(n,k))!=gt.end()) return gt[pll(n,k)];
      ^
ogledala.cpp:35:10: error: 'gt' was not declared in this scope
  return (gt[pll(n,k)] = g(n-1-n/2,k)+g(n/2,k));
          ^
ogledala.cpp: In function 'int main()':
ogledala.cpp:84:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(p<que.size()&&que[p]<=cnt+tmp.num) {
          ^
ogledala.cpp:87:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (p==que.size()) break;
        ^
ogledala.cpp:55: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:58: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:69:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&v);
                   ^