제출 #375257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
375257		8e7	Naan (JOI19_naan)	C++14	0 / 100	2 ms	620 KiB

naan

//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
• Subtask 2: 0 / 24
• Subtask 3: 0 / 71