| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 123857 |
2019-07-02T08:04:10 Z |
윤교준(#3030) |
Naan (JOI19_naan) |
C++14 |
|
4000 ms |
30136 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 = 1000000;
struct FRC {
FRC(lll a, lll b) : a(a), b(b) { norm(); }
FRC(lll a) : a(a), b(1) {}
FRC() : a(0), b(1) {}
ll 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;
}
ll g = gcd(abs(a), b);
if(g) {
a /= g;
b /= g;
}
}
lll floor() const { return a/b; }
FRC& snk() {
for(; MAXX < b;) {
b >>= 1;
a = (a+1) >> 1;
norm();
}
return *this;
}
FRC& rsnk() {
for(; MAXX < b;) {
b = (b+1) >> 1;
a >>= 1;
norm();
}
return *this;
}
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 {
if(floor() != A.floor()) return floor() < A.floor();
return (a-floor()*b)*A.b < b*(A.a-A.floor()*A.b);
}
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 nxtF(int i, FRC pv, FRC nd) {
pv.snk(); nd.snk();
if(nd <= 0) return pv;
if(pv >= K) return K+1;
int j = pv.floor();
{
FRC l = FRC(j+1) - pv;
l.rsnk();
if(nd <= (l * A[i][j+1]).rsnk())
return (pv + (nd / A[i][j+1]).snk()).snk();
nd = (nd - (l * A[i][j+1]).rsnk()).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])).snk();
pv = s;
FRC l = (nd / A[i][s+1]).snk();
return (pv + l).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);
for(int cnt = 1; cnt <= N; cnt++) {
FRC mnx(K+1);
int mni = -1;
for(int i = 1; i <= N; i++) if(!chk[i]) {
FRC t = nxtF(i, pos[cnt-1], nd[i]).snk();
if(t.b > MAXX/100) {
t.a += 5;
t.snk();
t.norm();
}
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 |
3 ms |
552 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 |
3 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
504 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 |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
508 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 |
508 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 |
504 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 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 |
504 KB |
Output is correct |
| 17 |
Correct |
3 ms |
632 KB |
Output is correct |
| 18 |
Correct |
3 ms |
504 KB |
Output is correct |
| 19 |
Correct |
3 ms |
632 KB |
Output is correct |
| 20 |
Correct |
3 ms |
504 KB |
Output is correct |
| 21 |
Correct |
3 ms |
504 KB |
Output is correct |
| 22 |
Correct |
3 ms |
504 KB |
Output is correct |
| 23 |
Correct |
2 ms |
504 KB |
Output is correct |
| 24 |
Correct |
3 ms |
504 KB |
Output is correct |
| 25 |
Correct |
3 ms |
504 KB |
Output is correct |
| 26 |
Correct |
2 ms |
504 KB |
Output is correct |
| 27 |
Correct |
3 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 |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
552 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 |
3 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
504 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 |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
504 KB |
Output is correct |
| 18 |
Correct |
3 ms |
504 KB |
Output is correct |
| 19 |
Correct |
3 ms |
508 KB |
Output is correct |
| 20 |
Correct |
2 ms |
504 KB |
Output is correct |
| 21 |
Correct |
2 ms |
504 KB |
Output is correct |
| 22 |
Correct |
2 ms |
504 KB |
Output is correct |
| 23 |
Correct |
2 ms |
508 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 |
504 KB |
Output is correct |
| 27 |
Correct |
2 ms |
376 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 |
504 KB |
Output is correct |
| 32 |
Correct |
3 ms |
632 KB |
Output is correct |
| 33 |
Correct |
3 ms |
504 KB |
Output is correct |
| 34 |
Correct |
3 ms |
632 KB |
Output is correct |
| 35 |
Correct |
3 ms |
504 KB |
Output is correct |
| 36 |
Correct |
3 ms |
504 KB |
Output is correct |
| 37 |
Correct |
3 ms |
504 KB |
Output is correct |
| 38 |
Correct |
2 ms |
504 KB |
Output is correct |
| 39 |
Correct |
3 ms |
504 KB |
Output is correct |
| 40 |
Correct |
3 ms |
504 KB |
Output is correct |
| 41 |
Correct |
2 ms |
504 KB |
Output is correct |
| 42 |
Correct |
3 ms |
504 KB |
Output is correct |
| 43 |
Correct |
962 ms |
8156 KB |
Output is correct |
| 44 |
Execution timed out |
4051 ms |
30136 KB |
Time limit exceeded |
| 45 |
Halted |
0 ms |
0 KB |
- |
