Submission #68834

#	Time	Username	Problem	Language	Result	Execution time	Memory
68834		imsifile	Hill Reconstruction (FXCUP3_hill)	C++98	100 / 100	563 ms	19860 KiB

hill

#include<stdio.h>
#include<queue>
using namespace std;

typedef long long lld;

lld gcd(lld a, lld b){ return b ? gcd(b,a%b) : a; }

struct frac {
	lld b, a; // b/a
	int cu, nx;
	frac(lld b_=0, lld a_=1, int cu_=0, int nx_=0){ b=b_, a=a_, cu=cu_, nx=nx_; }
	bool operator< (const frac& c) const {
		return b*c.a < c.b*a;
	}
	void print(){
		lld g = gcd(b,a); b/=g, a/=g;
		printf("%lld/%lld\n", b, a);
	}
};

priority_queue<frac> pq;

struct coord { lld x, y; } ba[303030];
int N, nxt[303030], prv[303030]; lld cement;

lld ccw(coord a, coord b, coord c){
	return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;
}

int main(){
	scanf("%d%lld", &N, &cement), cement *= 2;
	for(int i=0; i<N; i++) scanf("%lld", &ba[i].x);
	for(int i=0; i<N; i++) scanf("%lld", &ba[i].y);
	for(int i=0; i<N-1; i++){
		nxt[i]=i+1, prv[i+1]=i;
		pq.push(frac(ba[i+1].y-ba[i].y, ba[i+1].x-ba[i].x, i, i+1));
	}
	while(!pq.empty()){
		frac fi = pq.top(); pq.pop();
		if(nxt[fi.cu] != fi.nx || prv[fi.nx] != fi.cu) continue;
		if(fi.cu == 0){ fi.print(); break; }
		int a=prv[fi.cu], b=fi.cu, c=fi.nx;
		lld area = ccw(ba[a], ba[b], ba[c]);
		if(cement < area){ fi.print(); break; }
		cement -= area;
		nxt[a]=c, prv[c]=a;
		pq.push(frac(ba[c].y-ba[a].y, ba[c].x-ba[a].x, a, c));
	}
	return 0;
}

Compilation message (stderr)

hill.cpp: In function 'int main()':
hill.cpp:32:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &N, &cement), cement *= 2;
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
hill.cpp:33:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%lld", &ba[i].x);
                         ~~~~~^~~~~~~~~~~~~~~~~~
hill.cpp:34:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%lld", &ba[i].y);
                         ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 32 / 32
• Subtask 2: 68 / 68