Submission #375279

#	Time	Username	Problem	Language	Result	Execution time	Memory
375279		8e7	Naan (JOI19_naan)	C++14	0 / 100	1 ms	364 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;
	}
	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];
	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]) * frac(v[p1 ^ 1][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 cf = zero;
		vector<frac> ans;
		int poss = 1;
		for (int i = 0;i < n;i++) {
			frac num = zero;
			//cout << "  " << i << " " << endl;
			while (true) {
				//cout << ind << " " << cf.a << " " << cf.b << endl;
				if (!(num < goal[p[i]])) {
					break;
				}
				if (ind >= l) {
					poss = 0;
					break;
				}
				frac add = frac(v[p[i]][ind]) * (frac(1) - cf);
				//cout << add.a << "  " << add.b << endl;
				if (num + add > goal[p[i]]) {
					cf = cf + (goal[p[i]] - num) / frac(v[p[i]][ind]);
					//cout << 1 << endl;
					ans.push_back(frac(ind) + cf);
					break;
				} else {
					num = num + (frac(1) - cf) * frac(v[p[i]][ind]);
					if (cf > zero) cf = zero;
					ind++;
				}
			}
		}
		if (poss) {
			for (auto i:ans) cout << i.a << " " << i.b << endl;
			for (int i:p) cout << i+1 << " ";
			cout << endl;
			return 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()));
	cout << -1 << endl;
}
/*
2 5
2 7 1 8 2
3 1 4 1 5


6 1
1
2
3
4
5
6
7

5 3
2 3 1
1 1 1
2 2 1
1 2 2
1 2 1
 */

• Subtask 1: 0 / 5
• Subtask 2: 0 / 24
• Subtask 3: 0 / 71