oj.uz

Submission #68834

# Submission time Handle Problem Language Result Execution time Memory
68834 2018-08-18T17:41:56 Z imsifile Hill Reconstruction (FXCUP3_hill) C++
100 / 100
 563 ms 19860 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 376 KB Output is correct
2 Correct 4 ms 480 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 628 KB Output is correct
6 Correct 4 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 376 KB Output is correct
2 Correct 4 ms 480 KB Output is correct
3 Correct 3 ms 480 KB Output is correct
4 Correct 3 ms 620 KB Output is correct
5 Correct 3 ms 628 KB Output is correct
6 Correct 4 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 166 ms 19720 KB Output is correct
10 Correct 147 ms 19720 KB Output is correct
11 Correct 563 ms 19804 KB Output is correct
12 Correct 211 ms 19808 KB Output is correct
13 Correct 87 ms 19808 KB Output is correct
14 Correct 81 ms 19808 KB Output is correct
15 Correct 175 ms 19808 KB Output is correct
16 Correct 209 ms 19860 KB Output is correct
17 Correct 165 ms 19860 KB Output is correct
18 Correct 89 ms 19860 KB Output is correct
19 Correct 128 ms 19860 KB Output is correct