| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 560547 |
2022-05-11T16:54:55 Z |
blue |
Naan (JOI19_naan) |
C++17 |
|
522 ms |
64044 KB |
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
const ll mx = 2'000;
int N, L;
struct frac
{
ll n;
ll d;
};
bool operator < (frac A, frac B)
{
return A.n*B.d < B.n*A.d;
}
bool operator == (frac A, frac B)
{
return A.n*B.d == B.n*A.d;
}
bool operator > (frac A, frac B)
{
return B < A;
}
bool operator <= (frac A, frac B)
{
return A.n*B.d <= B.n*A.d;
}
frac operator + (frac A, frac B)
{
return {A.n*B.d + B.n*A.d, A.d*B.d};
}
frac operator - (frac A, frac B)
{
return {A.n*B.d - B.n*A.d, A.d*B.d};
}
frac operator / (frac A, frac B)
{
return {A.n*B.d, B.n*A.d};
}
vvll V(1+mx, vll(1+mx, 0));
frac getVpref(int p, frac i)
{
if(i.n == i.d * L)
return {V[p][L], 1};
// return V[p][i.n/i.d] + (V[i.n/i.d + 1] - V[i.n/i.d]) * ((i.n % i.d) / i.d);
return frac{V[p][i.n/i.d]*i.d + (V[p][i.n/i.d + 1] - V[p][i.n/i.d]) * (i.n % i.d), i.d};
}
int main()
{
cin >> N >> L;
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= L; j++)
{
cin >> V[i][j];
V[i][j] += V[i][j-1];
}
}
vi visit(1+N, 0);
vector<frac> X;
vector<int> P;
X.push_back({0, 1});
vector<frac> curr(1+N, frac{0, 1});
int xct = 0;
for(int t = 1; t < N; t++)
{
int bestp = -1;
for(int i = 1; i <= N; i++)
{
if(visit[i]) continue;
while(getVpref(i, curr[i]) < getVpref(i, X.back()) + frac{V[i][L], N})
{
xct++;
if(xct >= 20'000'000)
assert(0);
if(curr[i].d == 1)
{
if(frac{V[i][curr[i].n + 1], 1} <= getVpref(i, X.back()) + frac{V[i][L], N})
curr[i].n++;
else
{
frac thisfrac = (getVpref(i, X.back()) + frac{V[i][L], N} - getVpref(i, curr[i])) / frac{V[i][curr[i].n + 1] - V[i][curr[i].n], 1};
curr[i] = curr[i] + thisfrac;
}
}
else
{
curr[i] = frac{curr[i].n / curr[i].d + 1, 1};
}
}
if(bestp == -1 || curr[bestp] > curr[i])
bestp = i;
}
visit[bestp] = 1;
P.push_back(bestp);
X.push_back(curr[bestp]);
}
for(int i = 1; i <= N; i++)
if(!visit[i])
P.push_back(i);
for(int i = 1; i <= N-1; i++)
cout << X[i].n << ' ' << X[i].d << '\n';
for(int p : P)
cout << p << ' ';
cout << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 2 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 3 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 4 |
Correct |
14 ms |
31672 KB |
Output is correct |
| 5 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 6 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 7 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 8 |
Correct |
14 ms |
31668 KB |
Output is correct |
| 9 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 10 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 11 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 12 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 13 |
Correct |
15 ms |
31600 KB |
Output is correct |
| 14 |
Correct |
14 ms |
31628 KB |
Output is correct |
| 15 |
Correct |
15 ms |
31608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 2 |
Correct |
15 ms |
31608 KB |
Output is correct |
| 3 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 4 |
Correct |
15 ms |
31588 KB |
Output is correct |
| 5 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 6 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 7 |
Correct |
15 ms |
31632 KB |
Output is correct |
| 8 |
Correct |
14 ms |
31652 KB |
Output is correct |
| 9 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 10 |
Correct |
16 ms |
31676 KB |
Output is correct |
| 11 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 12 |
Correct |
16 ms |
31612 KB |
Output is correct |
| 13 |
Correct |
16 ms |
31600 KB |
Output is correct |
| 14 |
Correct |
16 ms |
31628 KB |
Output is correct |
| 15 |
Correct |
15 ms |
31676 KB |
Output is correct |
| 16 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 17 |
Correct |
18 ms |
31700 KB |
Output is correct |
| 18 |
Correct |
17 ms |
31700 KB |
Output is correct |
| 19 |
Correct |
16 ms |
31584 KB |
Output is correct |
| 20 |
Correct |
18 ms |
31828 KB |
Output is correct |
| 21 |
Correct |
20 ms |
31636 KB |
Output is correct |
| 22 |
Correct |
17 ms |
31712 KB |
Output is correct |
| 23 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 24 |
Correct |
17 ms |
31672 KB |
Output is correct |
| 25 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 26 |
Correct |
15 ms |
31680 KB |
Output is correct |
| 27 |
Correct |
15 ms |
31716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 2 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 3 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 4 |
Correct |
14 ms |
31672 KB |
Output is correct |
| 5 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 6 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 7 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 8 |
Correct |
14 ms |
31668 KB |
Output is correct |
| 9 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 10 |
Correct |
13 ms |
31700 KB |
Output is correct |
| 11 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 12 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 13 |
Correct |
15 ms |
31600 KB |
Output is correct |
| 14 |
Correct |
14 ms |
31628 KB |
Output is correct |
| 15 |
Correct |
15 ms |
31608 KB |
Output is correct |
| 16 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 17 |
Correct |
15 ms |
31608 KB |
Output is correct |
| 18 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 19 |
Correct |
15 ms |
31588 KB |
Output is correct |
| 20 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 21 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 22 |
Correct |
15 ms |
31632 KB |
Output is correct |
| 23 |
Correct |
14 ms |
31652 KB |
Output is correct |
| 24 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 25 |
Correct |
16 ms |
31676 KB |
Output is correct |
| 26 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 27 |
Correct |
16 ms |
31612 KB |
Output is correct |
| 28 |
Correct |
16 ms |
31600 KB |
Output is correct |
| 29 |
Correct |
16 ms |
31628 KB |
Output is correct |
| 30 |
Correct |
15 ms |
31676 KB |
Output is correct |
| 31 |
Correct |
15 ms |
31700 KB |
Output is correct |
| 32 |
Correct |
18 ms |
31700 KB |
Output is correct |
| 33 |
Correct |
17 ms |
31700 KB |
Output is correct |
| 34 |
Correct |
16 ms |
31584 KB |
Output is correct |
| 35 |
Correct |
18 ms |
31828 KB |
Output is correct |
| 36 |
Correct |
20 ms |
31636 KB |
Output is correct |
| 37 |
Correct |
17 ms |
31712 KB |
Output is correct |
| 38 |
Correct |
14 ms |
31700 KB |
Output is correct |
| 39 |
Correct |
17 ms |
31672 KB |
Output is correct |
| 40 |
Correct |
16 ms |
31700 KB |
Output is correct |
| 41 |
Correct |
15 ms |
31680 KB |
Output is correct |
| 42 |
Correct |
15 ms |
31716 KB |
Output is correct |
| 43 |
Runtime error |
522 ms |
64044 KB |
Execution killed with signal 6 |
| 44 |
Halted |
0 ms |
0 KB |
- |
