Submission #72241

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72241	2018-08-26T06:18:36 Z	이시대의진정한망겜스타투(#2267, cki86201, ainta)	Hill Reconstruction (FXCUP3_hill)	C++17	Compilation error	0 ms	0 KB

hill

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;

int N;
pll p[300030];
ll C;
pll operator-(pll a, pll b) { return pll(a.Fi - b.Fi, a.Se - b.Se); }
pll operator+(pll a, pll b) { return pll(a.Fi + b.Fi, a.Se + b.Se); }
ll operator/(pll a, pll b) { return a.Fi * b.Se - a.Se * b.Fi; }
int nxt[600030], pre[600030];
pll data[600060];
int chk[600060];

ll gc(ll x, ll y) { return y == 0 ? x : gc(y, x%y); }

void upd(pll &a, pll b) {
	if(a.Se * b.Fi < b.Se * a.Fi) a = b;
}

struct str {
	str(){}
	str(ll dx, ll dy) { p = pll(dx, dy); }
	str(pll p) : p(p) {}
	pll p;
	bool operator<(const str &rhs) const {
		return p.Se * rhs.p.Fi < p.Fi * rhs.p.Se;
	}
};

void output(pll p) {
	ll g = gc(p.Fi, p.Se);
	p.Fi /= g;
	p.Se /= g;
	printf("%lld/%lld\n", p.Se, p.Fi);
}

int main() {
	scanf("%d", &N);
	scanf("%lld", &C);
	C *= 2;
	for(int i=1;i<=N;i++) {
		scanf("%lld", &p[i].Fi);
	}
	for(int i=1;i<=N;i++) {
		scanf("%lld", &p[i].Se);
	}
	
	for(int i=1;i<N;i++) data[i] = p[i+1] - p[i];
	for(int i=0;i<=N;i++) {
		nxt[i] = i + 1;
		pre[i] = i - 1;
	}
	priority_queue <pair<str, int> > pq;
	for(int i=2;i<=N;i++) {
		pq.push(make_pair(str(p[i] - p[i-1]), i - 1));
	}
	int cs = N;
	pll ans = pll(0, 1);
	while(!pq.empty()) {
		auto pr = pq.top(); pq.pop();
		if(chk[pr.Se] == 1) continue;
		if(pre[pr.Se] == 0 || szz(pq) == 0) { output(pr.Fi.p); return 0; }
		pll me = pr.Fi.p;
		if(ans.Se * me.Fi > ans.Fi * me.Se) ans = me;
		pll prp = data[pre[pr.Se]];
		ll val = prp / (prp + me);
		if(C < val) { output(pr.Fi.p); return 0; }
		C -= val;
		int u = pr.Se, v = pre[u];
		chk[u] = chk[v] = 1;
		int nw = ++cs;
		pre[nw] = pre[v];
		nxt[nw] = nxt[u];
		pre[nxt[u]] = nw;
		nxt[pre[v]] = nw;
		data[nw] = prp + me;
		pq.push(make_pair(data[nw], nw));
	}
	output(ans);
	return 0;
}

Compilation message

hill.cpp: In function 'int main()':
hill.cpp:76:23: error: reference to 'data' is ambiguous
  for(int i=1;i<N;i++) data[i] = p[i+1] - p[i];
                       ^~~~
hill.cpp:39:5: note: candidates are: pll data [600060]
 pll data[600060];
     ^~~~
In file included from /usr/include/c++/7/deque:65:0,
                 from /usr/include/c++/7/queue:60,
                 from hill.cpp:7:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
hill.cpp:93:13: error: reference to 'data' is ambiguous
   pll prp = data[pre[pr.Se]];
             ^~~~
hill.cpp:39:5: note: candidates are: pll data [600060]
 pll data[600060];
     ^~~~
In file included from /usr/include/c++/7/deque:65:0,
                 from /usr/include/c++/7/queue:60,
                 from hill.cpp:7:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
hill.cpp:104:3: error: reference to 'data' is ambiguous
   data[nw] = prp + me;
   ^~~~
hill.cpp:39:5: note: candidates are: pll data [600060]
 pll data[600060];
     ^~~~
In file included from /usr/include/c++/7/deque:65:0,
                 from /usr/include/c++/7/queue:60,
                 from hill.cpp:7:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
hill.cpp:105:21: error: reference to 'data' is ambiguous
   pq.push(make_pair(data[nw], nw));
                     ^~~~
hill.cpp:39:5: note: candidates are: pll data [600060]
 pll data[600060];
     ^~~~
In file included from /usr/include/c++/7/deque:65:0,
                 from /usr/include/c++/7/queue:60,
                 from hill.cpp:7:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
hill.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
hill.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &C);
  ~~~~~^~~~~~~~~~~~
hill.cpp:70:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &p[i].Fi);
   ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &p[i].Se);
   ~~~~~^~~~~~~~~~~~~~~~~~