oj.uz

Submission #375250

# Submission time Handle Problem Language Result Execution time Memory
375250 2021-03-09T05:27:33 Z 8e7 Naan (JOI19_naan) C++14
0 / 100
 1 ms 620 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define maxn 2005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
ll v[10][maxn], pref[10][maxn];


ll gcd(ll a, ll b) {
	if (a > b) swap(a, b);
	return a == 0 ? b : gcd(b % a, a);
}
struct frac{
	ll a, b;
	frac() {
		a = 0, b = 1;
	}
	frac(ll x) {
		a = x, b = 1;
	}
	frac(ll x, ll y) {
		a = x, b = y;
	}
	void sim() {
		ll g = gcd(a > 0 ? a : -a, b > 0 ? b : -b);
		a /= g, b /= g;
	}
	frac operator + (frac f) {
		frac ret = frac(a * f.b + b * f.a, b * f.b);
		ret.sim();
		return ret;
	}
	frac operator -(frac f) {
		frac ret = frac(a * f.b - b * f.a, b * f.b);
		ret.sim();
		return ret;
	}
	frac operator *(frac f) {
		frac ret = frac(a * f.a, b * f.b);
		ret.sim();
		return ret;
	}
	frac operator /(frac f) {
		frac ret = frac(a * f.b, b * f.a);
		ret.sim();
		return ret;
	}
	bool operator <(frac f) {
		return a * f.b < b * f.a;
	}
	bool operator >(frac f) {
		return a * f.b > b * f.a;
	}
};
const frac zero = frac(0, 1);

int main() {
	io
	//frac res =frac(1, 4) - frac(4, 10);
	//cout << res.a << " " << res.b << endl;
	int n, l;
	cin >> n >> l;
	vector<int> p;
	//frac goal[6];
	frac goal[2];
	for (int i = 0;i < n;i++) {
		ll num = 0;
		for (int j = 0;j < l;j++) {
			cin >> v[i][j];
			num += v[i][j];
		}
		goal[i] = frac(num, n);
		//goal[i].sim();
		//p.push_back(i);
	}
	for (int p1 = 0;p1 < 2;p1++) {
		frac cur = zero;
		for (int i = 0;i < l;i++) {
			if (cur + v[p1][i] > goal[p1]) {
				frac rem = frac(1) - (goal[p1] - cur) / v[p1][i];
				for (int j = i + 1;j < l;j++) rem = rem + frac(v[p1 ^ 1][j]);
				if (!(rem < goal[p1 ^ 1])) {
					frac pos = frac(i) + (goal[p1] - cur) / v[p1][i];
					pos.sim();
					cout << pos.a << " " << pos.b << endl;
					cout << p1 + 1 << " " << (p1 ^ 1) + 1 << endl;
					return 0;
				}
				break;
			}
			cur = cur + v[p1][i];
		}
	}
	cout << -1 << endl;
	/*
	do {
		int ind = 0;
		frac cur = zero;
		vector<frac> ans;
		int poss = 0;

		for (int i = 0;i < l;i++) {
			frac add = frac(v[p[ind]][i]);
			if (goal[p[ind]] < cur + add) {
				frac part = (goal[p[ind]] - cur) / add;
				ind++;
				if (!(part > zero)) {
					ans.push_back(frac(i));
					i--;
				} else {
					ans.push_back(frac(i) + part);

				}

			}
		}


	} while (next_permutation(p.begin(), p.end()));
	*/
}
/*
2 5
2 7 1 8 2
3 1 4 1 5
 */

Subtask #1
0 / 5.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 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 Incorrect 1 ms 364 KB Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000]
9 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Runtime error 1 ms 620 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 71.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 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 Incorrect 1 ms 364 KB Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000]
9 Halted 0 ms 0 KB -