| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 375281 |
2021-03-09T06:09:49 Z |
8e7 |
Naan (JOI19_naan) |
C++14 |
|
1 ms |
384 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;
}
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;
if (i < n) 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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Integer parameter [name=P_i] equals to 39, violates the range [1, 2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Integer parameter [name=P_i] equals to 46473, violates the range [1, 2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Integer parameter [name=P_i] equals to 39, violates the range [1, 2] |
| 2 |
Halted |
0 ms |
0 KB |
- |
