oj.uz

Submission #377978

# Submission time Handle Problem Language Result Execution time Memory
377978 2021-03-15T16:43:22 Z pit4h Naan (JOI19_naan) C++14
29 / 100
 440 ms 8640 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 2e3+1;
int n, l, v[MAXN][MAXN], pref[MAXN][MAXN];

struct Q {
	ll p, q;
	void norm() { ll g = __gcd(p, q); p /= g, q /= g; }
	Q() { p=0, q=1; }
	Q(ll _p, ll _q) { p=_p, q=_q, norm(); }
	bool operator<(const Q& other) const {
		return (ll)p * other.q < (ll)other.p * q;
	}
	Q operator+(const Q& other) const {
		return Q(p*other.q + other.p*q, q*other.q); 
	}
	Q operator-(const Q& other) const {
		return Q(p*other.q - other.p*q, q*other.q); 
	}
	Q operator*(const Q& other) const {
		return Q(p*other.p, q*other.q); 
	}
	Q operator/(const Q& other) const {
		return Q(p*other.q, q*other.p);
	}
	ll floor() { return p/q; };
};

Q calc(Q start, int it) {
	int st = start.floor();
	int lo = st, hi = l-1, res=st;
	Q beg = Q(v[it][st], 1) * (Q(st+1, 1) - start);
	//cerr<<"  "<<beg.p<<' '<<beg.q<<'\n';
	Q score = Q(0, 1); 
	while(lo <= hi) {
		int mid = (lo+hi)/2;
		Q cur_score = beg + Q(pref[it][mid] - pref[it][st], 1);
		//cerr<<"  "<<mid<<": "<<cur_score.p<<' '<<cur_score.q<<'\n';
		if(cur_score < Q(pref[it][l], n)) {
			//cerr<<".\n";
			score = cur_score;
			res = mid + 1;
			lo = mid+1;
		}
		else {
			hi = mid-1;
		}
	}
	//cerr<<"  "<<st<<' '<<res<<' '<<score.p<<' '<<score.q<<'\n';
	Q ret;
	if(res>st) {
		ret = Q(res, 1) + (Q(pref[it][l], n) - score) / Q(v[it][res], 1);
	}
	else {
		ret = start + (Q(pref[it][l], n) - score) / Q(v[it][res], 1);
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>l;
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=l; ++j) {
			cin>>v[i][j];
			pref[i][j] = pref[i][j-1] + v[i][j];
		}
	}
	vector<int> people;
	for(int i=1; i<=n; ++i) people.push_back(i);

	Q start(1, 1);
	vector<int> perm;
	vector<Q> X;
	for(int iter=1; iter<=n; ++iter) {
		int& best = people[0];
		Q bestv;
		//cerr<<"iter: "<<iter<<'\n';
		for(int& i: people) {
			//cerr<<i<<'\n';
			Q curv = calc(start, i);
			//cerr<<' '<<curv.p<<' '<<curv.q<<'\n';
			if(i==people[0] || curv < bestv) {
				swap(best, i);
				bestv = curv;
			}
		}
		perm.push_back(best);

		start = bestv;
		best = people.back();
		people.pop_back();
		
		if(iter < n) X.push_back(start);
	}

	for(auto& i: X) {
		i = i - Q(1, 1);
		cout<<i.p<<' '<<i.q<<'\n';	
	}
	for(auto i: perm) {
		cout<<i<<' ';
	}
	cout<<'\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 2 ms 492 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 2 ms 492 KB Output is correct
21 Correct 2 ms 492 KB Output is correct
22 Correct 1 ms 492 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 2 ms 492 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 2 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 492 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 492 KB Output is correct
30 Correct 2 ms 492 KB Output is correct
31 Correct 2 ms 492 KB Output is correct
32 Correct 2 ms 492 KB Output is correct
33 Correct 2 ms 492 KB Output is correct
34 Correct 2 ms 492 KB Output is correct
35 Correct 2 ms 492 KB Output is correct
36 Correct 2 ms 492 KB Output is correct
37 Correct 1 ms 492 KB Output is correct
38 Correct 1 ms 364 KB Output is correct
39 Correct 1 ms 492 KB Output is correct
40 Correct 1 ms 492 KB Output is correct
41 Correct 1 ms 364 KB Output is correct
42 Correct 2 ms 492 KB Output is correct
43 Incorrect 440 ms 8640 KB Integer parameter [name=A_i] equals to 2109834534371, violates the range [1, 2000000000000]
44 Halted 0 ms 0 KB -