oj.uz

Submission #30593

# Submission time Handle Problem Language Result Execution time Memory
30593 2017-07-25T08:25:07 Z kajebiii None (KOI16_dist) C++14
2 / 100
 119 ms 3084 KB 
#include <stdio.h>
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 3e4 + 100;

int sign(ll x) {return (x>0) - (x<0);}
struct PT {
	int x, y;
	PT() : x(0), y(y) {}
	PT(int xx, int yy) : x(xx), y(yy) {}
	PT operator-(const PT &o) const {return PT(x-o.x, y-o.y);}
	int ccw(const PT &o) const {return sign(1ll * x * o.y - 1ll * y * o.x);}
	int ccw(const PT &a, const PT &b) const {return (a-*this).ccw(b-*this);}
	bool operator<(const PT &o) const {
		if(y != o.y) return y < o.y;
		return x < o.x;
	}
	bool operator==(const PT &o) const {
		return x == o.x && y == o.y;
	}
};

int N, T, Nr[MAX_N][4];
ll getV(int day) {
	vector<PT> Ps;
	for(int i=0; i<N; i++) Ps.push_back(PT(Nr[i][0] + Nr[i][2] * day, Nr[i][1] + Nr[i][3] * day));
	sort(ALL(Ps)); 
	Ps.erase(unique(ALL(Ps)), Ps.end());
	int pN = SZ(Ps);
//	printf("day : %d\n", day); for(int i=0; i<pN; i++) printf("[%d %d] ", Ps[i].x, Ps[i].y); puts("");

	sort(Ps.begin()+1, Ps.end(), [&](PT a, PT b) {
		int cv = Ps[0].ccw(a, b);
		assert(cv != 0);
		return cv == 1;
	});

	vector<PT> Cv;
	for(int i=0; i<pN; i++) {
		while(SZ(Cv) >= 2 && Cv[SZ(Cv)-2].ccw(Cv.back(), Ps[i]) <= 0) Cv.pop_back();
		Cv.push_back(Ps[i]);
	}

	int cN = SZ(Cv);
	ll maxV = 0;
	for(int i=0, j=0; i<cN; i++) {
		if(i == j) j = (j+1) % cN;
		int ni = (i+1) % cN, nj = (j+1) % cN;
		while((Cv[ni]-Cv[i]).ccw(Cv[nj]-Cv[j]) > 0) nj = (nj+1) % cN, j = (j+1) % cN;
		PT diff = Cv[i] - Cv[j];
		maxV = max(maxV, 1ll*diff.x*diff.x + 1ll*diff.y*diff.y);
	}
	return maxV;
}

int ans = -1; ll minD = LINF;
void push(int ix, ll val) {
//	printf("%d is %lld\n", ix, val);
	if(minD > val || (minD == val && ans > ix) ) minD = val, ans = ix;
}
int main() {
	cin >> N >> T;
	for(int i=0; i<N; i++) for(int j=0; j<4; j++) scanf("%d", &Nr[i][j]);

	for(int l=0, r=T; l<=r; ) {
		if(r - l <= 5) {
			for(int i=l; i<=r; i++) push(i, getV(i));
			break;
		}
		int m0 = (l+l+r) / 3, m1 = (l+r+r) / 3;
		ll v0 = getV(m0), v1 = getV(m1);
		if(v0 <= v1) r = m1 - 1, push(m1, v1); else l = m0 + 1, push(m0, v0);
	}
	printf("%d\n%lld\n", ans, minD);
	return 0;
}

Compilation message

dist.cpp: In constructor 'PT::PT()':
dist.cpp:23:2: warning: 'PT::y' is initialized with itself [-Winit-self]
  PT() : x(0), y(y) {}
  ^
dist.cpp: In function 'int main()':
dist.cpp:77:70: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) for(int j=0; j<4; j++) scanf("%d", &Nr[i][j]);
                                                                      ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2492 KB Output is correct
2 Correct 0 ms 2492 KB Output is correct
3 Correct 0 ms 2492 KB Output is correct
4 Correct 0 ms 2492 KB Output is correct
5 Correct 0 ms 2492 KB Output is correct
6 Correct 0 ms 2492 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 0 ms 2492 KB Output is correct
9 Correct 0 ms 2492 KB Output is correct
10 Correct 0 ms 2492 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2492 KB Output is correct
2 Correct 0 ms 2492 KB Output is correct
3 Correct 0 ms 2492 KB Output is correct
4 Correct 0 ms 2492 KB Output is correct
5 Correct 0 ms 2492 KB Output is correct
6 Correct 0 ms 2492 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 0 ms 2492 KB Output is correct
9 Correct 0 ms 2492 KB Output is correct
10 Correct 0 ms 2492 KB Output is correct
11 Correct 13 ms 2492 KB Output is correct
12 Correct 13 ms 2492 KB Output is correct
13 Correct 16 ms 2492 KB Output is correct
14 Runtime error 6 ms 2496 KB Execution killed because of forbidden syscall gettid (186)
15 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 3080 KB Output is correct
2 Correct 106 ms 3080 KB Output is correct
3 Runtime error 56 ms 3084 KB Execution killed because of forbidden syscall gettid (186)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2492 KB Output is correct
2 Correct 0 ms 2492 KB Output is correct
3 Correct 0 ms 2492 KB Output is correct
4 Correct 0 ms 2492 KB Output is correct
5 Correct 0 ms 2492 KB Output is correct
6 Correct 0 ms 2492 KB Output is correct
7 Correct 0 ms 2492 KB Output is correct
8 Correct 0 ms 2492 KB Output is correct
9 Correct 0 ms 2492 KB Output is correct
10 Correct 0 ms 2492 KB Output is correct
11 Correct 13 ms 2492 KB Output is correct
12 Correct 13 ms 2492 KB Output is correct
13 Correct 16 ms 2492 KB Output is correct
14 Runtime error 6 ms 2496 KB Execution killed because of forbidden syscall gettid (186)
15 Halted 0 ms 0 KB -