| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 375248 |
2021-03-09T05:26:55 Z |
8e7 |
Naan (JOI19_naan) |
C++14 |
|
1 ms |
364 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[i]) {
frac rem = frac(1) - (goal[i] - 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[i] - 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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Not a fair distribution. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Not a fair distribution. |
| 2 |
Halted |
0 ms |
0 KB |
- |
