| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 201277 |
2020-02-10T05:54:01 Z |
BThero |
Naan (JOI19_naan) |
C++17 |
|
40 ms |
63480 KB |
// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int MAXN = (int)2e3 + 5;
struct Ratio {
ll a, b;
Ratio() {
a = 0;
b = 1;
}
Ratio(ll a, ll b) : a(a), b(b) {
ll g = __gcd(a, b);
a /= g;
b /= g;
}
} limS[MAXN], curS[MAXN], sep[MAXN];
int lcm(int a, int b) {
return a / __gcd(a, b) * b;
}
bool operator < (Ratio f, Ratio s) {
return f.a * s.b < f.b * s.a;
}
bool operator > (Ratio f, Ratio s) {
return s < f;
}
bool operator == (Ratio f, Ratio s) {
return !(f < s) && !(s < f);
}
bool operator <= (Ratio f, Ratio s) {
return f < s || f == s;
}
bool operator >= (Ratio f, Ratio s) {
return f > s || f == s;
}
Ratio operator + (Ratio f, Ratio s) {
int d = lcm(f.b, s.b);
return Ratio(f.a * d / f.b + s.a * d / s.b, d);
}
Ratio operator - (Ratio f, Ratio s) {
s.a *= -1;
return f + s;
}
Ratio operator * (Ratio f, Ratio s) {
return Ratio(f.a * s.a, f.b * s.b);
}
Ratio operator / (Ratio f, Ratio s) {
swap(s.a, s.b);
return f * s;
}
Ratio arr[MAXN][MAXN];
Ratio coef[MAXN];
int perm[MAXN];
int n, m;
void solve() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &arr[i][j].a);
arr[i][j].b = 1;
limS[i] = limS[i] + arr[i][j];
}
limS[i].b = n;
}
for (int i = 1; i <= n; ++i) {
perm[i] = i;
}
do {
int ptr = 1;
fill(curS + 1, curS + n + 1, Ratio(0, 1));
bool ok = 1;
for (int i = 1; i <= m; ++i) {
coef[i] = Ratio(1, 1);
}
for (int i = 1; i <= n; ++i) {
int id = perm[i];
//printf("! %d - %d/%d\n", ptr, coef[ptr].a, coef[ptr].b);
while (ptr <= m && curS[id] + arr[id][ptr] * coef[ptr] <= limS[id]) {
curS[id] = curS[id] + arr[id][ptr] * coef[ptr];
++ptr;
}
if (ptr > m) {
if (curS[id] < limS[id]) {
ok = 0;
}
break;
}
sep[i] = (limS[id] - curS[id]) / arr[id][ptr];
curS[id] = curS[id] + sep[i] * arr[id][ptr];
Ratio tmp = coef[ptr];
coef[ptr] = coef[ptr] - sep[i];
sep[i] = sep[i] + Ratio(ptr, 1) - tmp;
}
for (int i = 1; i <= n; ++i) {
ok &= (curS[i] >= limS[i]);
}
if (ok) {
for (int i = 1; i < n; ++i) {
printf("%lld %lld\n", sep[i].a, sep[i].b);
}
for (int i = 1; i <= n; ++i) {
printf("%d%c", perm[i], " \n"[i == n]);
}
return;
}
}
while (next_permutation(perm + 1, perm + n + 1));
printf("-1\n");
}
int main() {
int tt = 1;
while (tt--) {
solve();
}
return 0;
}
Compilation message
naan.cpp: In function 'void solve()':
naan.cpp:96:37: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
scanf("%d", &arr[i][j].a);
~~~~~~~~~~~~^
naan.cpp:92:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
naan.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &arr[i][j].a);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
63352 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
63352 KB |
Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000] |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 2 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 3 |
Correct |
35 ms |
63348 KB |
Output is correct |
| 4 |
Correct |
36 ms |
63352 KB |
Output is correct |
| 5 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 6 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 7 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 8 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 9 |
Correct |
38 ms |
63356 KB |
Output is correct |
| 10 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 11 |
Correct |
36 ms |
63480 KB |
Output is correct |
| 12 |
Correct |
40 ms |
63352 KB |
Output is correct |
| 13 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 14 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 15 |
Correct |
36 ms |
63352 KB |
Output is correct |
| 16 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 17 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 18 |
Correct |
36 ms |
63352 KB |
Output is correct |
| 19 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 20 |
Correct |
37 ms |
63480 KB |
Output is correct |
| 21 |
Correct |
37 ms |
63352 KB |
Output is correct |
| 22 |
Correct |
36 ms |
63352 KB |
Output is correct |
| 23 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 24 |
Correct |
36 ms |
63352 KB |
Output is correct |
| 25 |
Correct |
36 ms |
63352 KB |
Output is correct |
| 26 |
Correct |
35 ms |
63352 KB |
Output is correct |
| 27 |
Correct |
36 ms |
63352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
63352 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
63352 KB |
Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000] |
| 3 |
Halted |
0 ms |
0 KB |
- |
