oj.uz

Submission #68836

# Submission time Handle Problem Language Result Execution time Memory
68836 2018-08-18T17:44:31 Z 검수컵(#1978, imsifile) Hill Reconstruction (FXCUP3_hill) C++
100 / 100
 427 ms 19936 KB 
#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

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.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 3 ms 548 KB Output is correct
6 Correct 3 ms 628 KB Output is correct
7 Correct 3 ms 628 KB Output is correct
8 Correct 3 ms 628 KB Output is correct

Subtask #2
68.0 / 68.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 3 ms 548 KB Output is correct
6 Correct 3 ms 628 KB Output is correct
7 Correct 3 ms 628 KB Output is correct
8 Correct 3 ms 628 KB Output is correct
9 Correct 135 ms 19784 KB Output is correct
10 Correct 206 ms 19936 KB Output is correct
11 Correct 427 ms 19936 KB Output is correct
12 Correct 184 ms 19936 KB Output is correct
13 Correct 107 ms 19936 KB Output is correct
14 Correct 104 ms 19936 KB Output is correct
15 Correct 207 ms 19936 KB Output is correct
16 Correct 135 ms 19936 KB Output is correct
17 Correct 158 ms 19936 KB Output is correct
18 Correct 90 ms 19936 KB Output is correct
19 Correct 141 ms 19936 KB Output is correct