| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 123767 |
2019-07-02T06:27:09 Z |
윤교준(#3030) |
Naan (JOI19_naan) |
C++14 |
|
1534 ms |
8276 KB |
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef __int128_t lll;
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) : a(a), b(b) { norm(); }
FRC(lll a) : a(a), b(1) {}
FRC() : a(0), b(1) {}
lll a, b; // a / b
void prt() const { printf("%lld %lld\n", ll(a), ll(b)); }
void norm() {
if(!a) {
b = 1;
return;
}
if(b < 0) {
a = -a;
b = -b;
}
lll g = gcd(a < 0 ? -a : a, b);
if(g) {
a /= g;
b /= g;
}
}
FRC& snk() {
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;
}
ll floor() { return a/b; }
FRC operator + (const FRC &A) const {
return FRC(a*A.b + b*A.a, b*A.b);
}
FRC operator - (const FRC &A) const {
return FRC(a*A.b - b*A.a, b*A.b);
}
FRC operator * (const FRC &A) const {
return FRC(a*A.a, b*A.b);
}
FRC operator / (const FRC &A) const {
return FRC(a*A.b, b*A.a);
}
bool operator == (const FRC &A) const {
return a == A.a && b == A.b;
}
bool operator < (const FRC &A) const {
return lll(a)*A.b < lll(b)*A.a;
}
bool operator <= (const FRC &A) const {
return lll(a)*A.b <= lll(b)*A.a;
}
bool operator > (const FRC &A) const {
return lll(a)*A.b > lll(b)*A.a;
}
bool operator >= (const FRC &A) const {
return lll(a)*A.b >= lll(b)*A.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 nxtF(int i, FRC pv, FRC nd) {
if(nd <= 0) return pv;
if(pv >= K) return K+1;
int j = pv.floor();
{
FRC l = FRC(j+1) - pv;
if((nd/l).snk() <= A[i][j+1])
return pv + nd / A[i][j+1];
nd = nd - (l * A[i][j+1]).rsnk();
nd.snk();
pv = j+1;
}
j++;
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];
}
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);
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;
}
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 |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
508 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
508 KB |
Output is correct |
| 12 |
Correct |
3 ms |
504 KB |
Output is correct |
| 13 |
Correct |
3 ms |
504 KB |
Output is correct |
| 14 |
Correct |
2 ms |
504 KB |
Output is correct |
| 15 |
Correct |
2 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
632 KB |
Output is correct |
| 3 |
Correct |
3 ms |
632 KB |
Output is correct |
| 4 |
Correct |
3 ms |
632 KB |
Output is correct |
| 5 |
Correct |
3 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 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 |
632 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
2 ms |
504 KB |
Output is correct |
| 14 |
Correct |
3 ms |
632 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 |
632 KB |
Output is correct |
| 19 |
Correct |
3 ms |
632 KB |
Output is correct |
| 20 |
Correct |
3 ms |
632 KB |
Output is correct |
| 21 |
Correct |
3 ms |
632 KB |
Output is correct |
| 22 |
Correct |
3 ms |
632 KB |
Output is correct |
| 23 |
Correct |
2 ms |
504 KB |
Output is correct |
| 24 |
Correct |
3 ms |
632 KB |
Output is correct |
| 25 |
Correct |
3 ms |
632 KB |
Output is correct |
| 26 |
Correct |
2 ms |
504 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 |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
2 ms |
504 KB |
Output is correct |
| 5 |
Correct |
2 ms |
504 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
508 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
508 KB |
Output is correct |
| 12 |
Correct |
3 ms |
504 KB |
Output is correct |
| 13 |
Correct |
3 ms |
504 KB |
Output is correct |
| 14 |
Correct |
2 ms |
504 KB |
Output is correct |
| 15 |
Correct |
2 ms |
504 KB |
Output is correct |
| 16 |
Correct |
2 ms |
504 KB |
Output is correct |
| 17 |
Correct |
2 ms |
632 KB |
Output is correct |
| 18 |
Correct |
3 ms |
632 KB |
Output is correct |
| 19 |
Correct |
3 ms |
632 KB |
Output is correct |
| 20 |
Correct |
3 ms |
632 KB |
Output is correct |
| 21 |
Correct |
2 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 |
632 KB |
Output is correct |
| 27 |
Correct |
2 ms |
504 KB |
Output is correct |
| 28 |
Correct |
2 ms |
504 KB |
Output is correct |
| 29 |
Correct |
3 ms |
632 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 |
632 KB |
Output is correct |
| 34 |
Correct |
3 ms |
632 KB |
Output is correct |
| 35 |
Correct |
3 ms |
632 KB |
Output is correct |
| 36 |
Correct |
3 ms |
632 KB |
Output is correct |
| 37 |
Correct |
3 ms |
632 KB |
Output is correct |
| 38 |
Correct |
2 ms |
504 KB |
Output is correct |
| 39 |
Correct |
3 ms |
632 KB |
Output is correct |
| 40 |
Correct |
3 ms |
632 KB |
Output is correct |
| 41 |
Correct |
2 ms |
504 KB |
Output is correct |
| 42 |
Correct |
3 ms |
632 KB |
Output is correct |
| 43 |
Incorrect |
1534 ms |
8276 KB |
Not a fair distribution. |
| 44 |
Halted |
0 ms |
0 KB |
- |
