| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 123868 |
2019-07-02T08:19:06 Z |
윤교준(#3030) |
Naan (JOI19_naan) |
C++14 |
|
2 ms |
632 KB |
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef long long lll;
//typedef __int128_t lll;
//typedef long double ld;
typedef double ld;
lll gcd(lll a, lll b) { for(;b;a%=b,swap(a,b)){} return a; }
static unsigned char str[55000055], *p=str;
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() {
if(MAXX < b) {
ld t = ld(a) / b;
b = MAXX;
a = t*MAXX;
a++;
norm();
}
return *this;
}
FRC& rsnk() {
if(MAXX < b) {
ld t = ld(a) / b;
b = MAXX;
a = t*MAXX;
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];
int LS[MAXN];
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 = max(j, LS[i]-1), 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;
}
LS[i] = s;
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() {
fread(str, 1, 55000055, stdin);
rf(N) rf(K)
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= K; j++) {
rf(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;
}
Compilation message
naan.cpp: In function 'int main()':
naan.cpp:136:7: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(str, 1, 55000055, stdin);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
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 |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
508 KB |
Output is correct |
| 9 |
Correct |
2 ms |
504 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Runtime error |
2 ms |
504 KB |
Execution failed because the return code was nonzero |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
504 KB |
Output is correct |
| 9 |
Correct |
2 ms |
632 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 |
504 KB |
Output is correct |
| 14 |
Correct |
2 ms |
504 KB |
Output is correct |
| 15 |
Correct |
2 ms |
632 KB |
Output is correct |
| 16 |
Correct |
2 ms |
632 KB |
Output is correct |
| 17 |
Correct |
2 ms |
632 KB |
Output is correct |
| 18 |
Runtime error |
2 ms |
632 KB |
Execution failed because the return code was nonzero |
| 19 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
508 KB |
Output is correct |
| 9 |
Correct |
2 ms |
504 KB |
Output is correct |
| 10 |
Correct |
2 ms |
504 KB |
Output is correct |
| 11 |
Runtime error |
2 ms |
504 KB |
Execution failed because the return code was nonzero |
| 12 |
Halted |
0 ms |
0 KB |
- |
