| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 123836 |
2019-07-02T07:45:00 Z |
윤교준(#3030) |
Naan (JOI19_naan) |
C++14 |
|
2065 ms |
8188 KB |
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long double ld;
typedef long long ll;
typedef __int128_t lll;
inline void fuk() { puts("ERR!"); exit(-1); }
lll gcd(lll a, lll b) { for(;b;a%=b,swap(a,b)){} return a; }
const int MAXX = 1000000000;
const ll KEY = 6469693230ll;
struct FRC {
FRC(lll a, lll b, lll c) : a(a), b(b), c(c) { norm(); }
FRC(lll a, lll b) : a(a), b(b), c(0) { norm(); }
FRC(lll c) : a(0), b(1), c(c) {}
FRC() : a(0), b(1), c(0) {}
lll a, b, c; // c + a / b
void prt() const { printf("%lld %lld\n", ll(b*c+a), ll(b)); }
void norm() {
if(b < 0) {
a = -a;
b = -b;
c = -c;
}
lll g = gcd(a < 0 ? -a : a, b);
if(g) {
a /= g;
b /= g;
}
if(a < 0) {
lll t = (-a)/b + 1;
c -= t;
a += t*b;
}
c += a/b;
a %= b;
}
FRC& snk() {
/*
if(MAXX < b) {
ld t = ld(a)/b;
b = MAXX;
a = t*MAXX;
a++;
norm();
}
*/
for(; MAXX < b;) {
a = (a+1) >> 1;
b >>= 1;
norm();
}
return *this;
}
FRC& rsnk() {
for(; MAXX < b;) {
a >>= 1;
b = (b+1) >> 1;
norm();
}
return *this;
}
lll floor() const { return c; }
FRC mulrsnk(const FRC &A) const {
return ((FRC(c*A.c) + FRC(c*A.a, A.b).rsnk()).rsnk() + (FRC(a*A.c, b).rsnk() + FRC(a*A.a, b*A.b).rsnk()).rsnk()).rsnk();
}
FRC operator + (const FRC &A) const {
return FRC(a*A.b + b*A.a, b*A.b, c+A.c).snk();
}
FRC operator - (const FRC &A) const {
return FRC(a*A.b - b*A.a, b*A.b, c-A.c).rsnk();
}
FRC operator * (const FRC &A) const {
return ((FRC(c*A.c) + FRC(c*A.a, A.b).snk()).snk() + (FRC(a*A.c, b).snk() + FRC(a*A.a, b*A.b).snk()).snk()).snk();
}
FRC operator / (const FRC &A) const {
return operator * (FRC(A.b, A.c*A.b+A.a).snk());
}
bool operator == (const FRC &A) const {
return a == A.a && b == A.b && c == A.c;
}
bool operator < (const FRC &A) const {
if(c != A.c) return c < A.c;
return a*A.b < b*A.a;
}
bool operator <= (const FRC &A) const {
return operator == (A) || operator < (A);
}
bool operator > (const FRC &A) const {
return ! operator <= (A);
}
bool operator >= (const FRC &A) const {
return ! operator < (A);
}
};
const int MAXN = 2005;
const int MAXK = 2005;
ll AS[MAXN][MAXK];
int A[MAXN][MAXK];
FRC pos[MAXN], nd[MAXN];
int O[MAXN];
bitset<MAXN> chk;
int N, K;
FRC getF(int i, FRC sp, FRC ep) {
sp.snk(); ep.rsnk();
FRC ret;
if(sp.floor() == ep.floor()) {
ret = (ep-sp).rsnk() * A[i][sp.floor()+1];
ret.rsnk();
return ret;
}
int s = sp.floor()+1, e = ep.floor();
ret = ((FRC(s)-sp).rsnk() * A[i][s]).rsnk();
for(int j = s+1; j <= e; j++)
ret = (ret + A[i][j]).rsnk();
FRC t = ((ep-e).rsnk() * A[i][e+1]).rsnk();
return (ret + t).rsnk();
}
FRC nxtF(int i, FRC pv, FRC nd) {
nd.snk(); pv.snk();
if(nd <= 0) return pv;
if(pv >= K) return K+1;
int j = pv.floor();
{
FRC l = FRC(j+1) - pv;
if(nd <= l.rsnk().mulrsnk(A[i][j+1])) {
return (pv + (nd / A[i][j+1]).snk()).snk();
}
nd = nd - l.rsnk().mulrsnk(A[i][j+1]);
nd.snk();
pv = j+1;
}
j++;
if(nd == 0) return pv;
if(nd > AS[i][K]-AS[i][j]) return K+1;
int s = j, e = K-1; for(int m; s < e;) {
m = (s+e+1) >> 1;
if(nd <= AS[i][m]-AS[i][j]) e = m-1;
else s = m;
}
nd = nd - (AS[i][s]-AS[i][j]);
pv = s;
nd.snk();
return (pv + (nd / A[i][s+1]).snk()).snk();
}
int main() {
ios::sync_with_stdio(false);
cin >> N >> K;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= K; j++) {
cin >> A[i][j];
AS[i][j] = AS[i][j-1] + A[i][j];
}
}
for(int i = 1; i <= N; i++) nd[i] = FRC(AS[i][K], N).snk();
for(int cnt = 1; cnt <= N; cnt++) {
FRC mnx(K);
int mni = -1;
for(int i = 1; i <= N; i++) if(!chk[i]) {
FRC t = nxtF(i, pos[cnt-1], nd[i]);
t.snk();
if(t <= mnx) {
mnx = t;
mni = i;
}
}
if(mni < 0) exit(-1);
pos[cnt] = mnx;
O[cnt] = mni;
chk[mni] = true;
}
chk.reset();
for(int i = 1; i <= N; i++) {
if(O[i] < 1 || N < O[i] || chk[O[i]]) fuk();
chk[O[i]] = true;
}
pos[N] = K;
for(int i = 1; i <= N; i++) {
if(pos[i].a < 0 || pos[i].b <= 0 || MAXX < pos[i].b) fuk();
if(pos[i-1] >= pos[i]) fuk();
}
for(int oi = 1, i; oi <= N; oi++) {
i = O[oi];
FRC sum = getF(i, pos[oi-1], pos[oi]);
if(sum < nd[i]) fuk();
}
for(int i = 1; i < N; i++) pos[i].prt();
for(int i = 1; i <= N; i++) printf("%d ", O[i]);
puts("");
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
632 KB |
Output is correct |
| 3 |
Correct |
3 ms |
636 KB |
Output is correct |
| 4 |
Correct |
3 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
3 ms |
632 KB |
Output is correct |
| 8 |
Correct |
3 ms |
632 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
3 ms |
632 KB |
Output is correct |
| 11 |
Correct |
3 ms |
632 KB |
Output is correct |
| 12 |
Correct |
3 ms |
632 KB |
Output is correct |
| 13 |
Correct |
3 ms |
632 KB |
Output is correct |
| 14 |
Correct |
3 ms |
632 KB |
Output is correct |
| 15 |
Correct |
3 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
632 KB |
Output is correct |
| 2 |
Correct |
3 ms |
632 KB |
Output is correct |
| 3 |
Correct |
3 ms |
632 KB |
Output is correct |
| 4 |
Correct |
3 ms |
760 KB |
Output is correct |
| 5 |
Correct |
3 ms |
632 KB |
Output is correct |
| 6 |
Correct |
3 ms |
632 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
632 KB |
Output is correct |
| 9 |
Correct |
3 ms |
632 KB |
Output is correct |
| 10 |
Correct |
3 ms |
632 KB |
Output is correct |
| 11 |
Correct |
3 ms |
636 KB |
Output is correct |
| 12 |
Correct |
2 ms |
632 KB |
Output is correct |
| 13 |
Correct |
3 ms |
632 KB |
Output is correct |
| 14 |
Correct |
3 ms |
760 KB |
Output is correct |
| 15 |
Correct |
3 ms |
632 KB |
Output is correct |
| 16 |
Correct |
3 ms |
632 KB |
Output is correct |
| 17 |
Correct |
3 ms |
632 KB |
Output is correct |
| 18 |
Correct |
3 ms |
760 KB |
Output is correct |
| 19 |
Correct |
3 ms |
760 KB |
Output is correct |
| 20 |
Correct |
3 ms |
632 KB |
Output is correct |
| 21 |
Correct |
3 ms |
760 KB |
Output is correct |
| 22 |
Correct |
3 ms |
760 KB |
Output is correct |
| 23 |
Correct |
2 ms |
632 KB |
Output is correct |
| 24 |
Correct |
3 ms |
632 KB |
Output is correct |
| 25 |
Correct |
3 ms |
632 KB |
Output is correct |
| 26 |
Correct |
3 ms |
632 KB |
Output is correct |
| 27 |
Correct |
3 ms |
632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
3 ms |
632 KB |
Output is correct |
| 3 |
Correct |
3 ms |
636 KB |
Output is correct |
| 4 |
Correct |
3 ms |
632 KB |
Output is correct |
| 5 |
Correct |
2 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
632 KB |
Output is correct |
| 7 |
Correct |
3 ms |
632 KB |
Output is correct |
| 8 |
Correct |
3 ms |
632 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 KB |
Output is correct |
| 10 |
Correct |
3 ms |
632 KB |
Output is correct |
| 11 |
Correct |
3 ms |
632 KB |
Output is correct |
| 12 |
Correct |
3 ms |
632 KB |
Output is correct |
| 13 |
Correct |
3 ms |
632 KB |
Output is correct |
| 14 |
Correct |
3 ms |
632 KB |
Output is correct |
| 15 |
Correct |
3 ms |
632 KB |
Output is correct |
| 16 |
Correct |
2 ms |
632 KB |
Output is correct |
| 17 |
Correct |
3 ms |
632 KB |
Output is correct |
| 18 |
Correct |
3 ms |
632 KB |
Output is correct |
| 19 |
Correct |
3 ms |
760 KB |
Output is correct |
| 20 |
Correct |
3 ms |
632 KB |
Output is correct |
| 21 |
Correct |
3 ms |
632 KB |
Output is correct |
| 22 |
Correct |
2 ms |
504 KB |
Output is correct |
| 23 |
Correct |
2 ms |
632 KB |
Output is correct |
| 24 |
Correct |
3 ms |
632 KB |
Output is correct |
| 25 |
Correct |
3 ms |
632 KB |
Output is correct |
| 26 |
Correct |
3 ms |
636 KB |
Output is correct |
| 27 |
Correct |
2 ms |
632 KB |
Output is correct |
| 28 |
Correct |
3 ms |
632 KB |
Output is correct |
| 29 |
Correct |
3 ms |
760 KB |
Output is correct |
| 30 |
Correct |
3 ms |
632 KB |
Output is correct |
| 31 |
Correct |
3 ms |
632 KB |
Output is correct |
| 32 |
Correct |
3 ms |
632 KB |
Output is correct |
| 33 |
Correct |
3 ms |
760 KB |
Output is correct |
| 34 |
Correct |
3 ms |
760 KB |
Output is correct |
| 35 |
Correct |
3 ms |
632 KB |
Output is correct |
| 36 |
Correct |
3 ms |
760 KB |
Output is correct |
| 37 |
Correct |
3 ms |
760 KB |
Output is correct |
| 38 |
Correct |
2 ms |
632 KB |
Output is correct |
| 39 |
Correct |
3 ms |
632 KB |
Output is correct |
| 40 |
Correct |
3 ms |
632 KB |
Output is correct |
| 41 |
Correct |
3 ms |
632 KB |
Output is correct |
| 42 |
Correct |
3 ms |
632 KB |
Output is correct |
| 43 |
Runtime error |
2065 ms |
8188 KB |
Execution failed because the return code was nonzero |
| 44 |
Halted |
0 ms |
0 KB |
- |
