| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 123745 |
2019-07-02T06:02:21 Z |
윤교준(#3030) |
Naan (JOI19_naan) |
C++14 |
|
989 ms |
8744 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;
struct FRC {
FRC(ll a, ll b) : a(a), b(b) { norm(); }
FRC(ll a) : a(a), b(1) {}
FRC() : a(0), b(1) {}
ll a, b; // a / b
void prt() const { printf("%lld %lld\n", a, 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;
}
}
void snk() {
for(; MAXX < b;) {
a++;
norm();
}
}
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 * A[i][j+1])
return pv + nd / A[i][j+1];
nd = nd - l * A[i][j+1];
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;
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++) {
if(cnt == N) {
for(int i = 1; i <= N; i++) if(!chk[i]) O[N] = i;
break;
}
FRC mnx[2]; mnx[0] = mnx[1] = K+1;
int mni[2] = {-1, -1};
for(int i = 1; i <= N; i++) if(!chk[i]) {
FRC t = nxtF(i, 0, FRC(AS[i][K]) - nd[i]*(N-cnt));
int idx = i;
if(t <= mnx[0]) {
swap(t, mnx[0]);
swap(idx, mni[0]);
}
if(t <= mnx[1]) {
swap(t, mnx[1]);
swap(idx, mni[1]);
}
}
for(int i = 1; i <= N; i++) if(!chk[i]) {
FRC t = nxtF(i, pos[cnt-1], nd[i]);
if(t > K) continue;
if(t <= mnx[0] || (t <= mnx[1] && i == mni[0])) {
chk[i] = true;
O[cnt] = i;
pos[cnt] = t;
pos[cnt].snk();
break;
}
}
if(!O[cnt]) exit(-1);
}
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 |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
508 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 |
376 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 |
504 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
504 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
2 ms |
508 KB |
Output is correct |
| 14 |
Correct |
3 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 |
504 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 |
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 |
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 |
508 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 |
504 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 |
508 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 |
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 |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
508 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 |
376 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 |
504 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Correct |
2 ms |
504 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
2 ms |
508 KB |
Output is correct |
| 14 |
Correct |
3 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 |
504 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 |
504 KB |
Output is correct |
| 22 |
Correct |
2 ms |
504 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 |
3 ms |
632 KB |
Output is correct |
| 27 |
Correct |
2 ms |
508 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 |
504 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 |
508 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 |
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 |
Incorrect |
989 ms |
8744 KB |
Integer parameter [name=A_i] equals to -15660707, violates the range [1, 2000000000000] |
| 44 |
Halted |
0 ms |
0 KB |
- |
