| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 522688 |
2022-02-05T11:47:53 Z |
phamhoanghiep |
Naan (JOI19_naan) |
C++14 |
|
681 ms |
150160 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2002;
struct frac{
ll who;
ll num;
ll den;
frac (ll _w, ll _n, ll _d): who(_w), num(_n), den(_d) {
int x=__gcd(num,den);
num/=x; den/=x;
};
};
bool cmp(frac a, frac b) {
if(a.who<b.who) return 1;
if(a.who>b.who) return 0;
return a.num*b.den<b.num*a.den;
}
vector<frac> split[maxn];
vector<frac> ans;
ll v[maxn][maxn];
ll sum[maxn];
int n,l;
int p[maxn];
bool used[maxn];
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>l;
for(int i=0 ; i<n ; i++) {
for(int j=0 ; j<l ; j++) {
cin>>v[i][j];
sum[i]+=v[i][j];
}
}
for(int i=0 ; i<n ; i++) {
ll cur=0;
ll pos=0;
for(int j=1 ; j<n ; j++) {
while((cur+v[i][pos])*n<=sum[i]*j) cur+=v[i][pos++];
ll rem=sum[i]*j-cur*n;
split[i].push_back(frac(pos,rem,n*v[i][pos]));
}
split[i].push_back(frac(l,0,1));
}
for(int i=0 ; i<n ; i++) {
int nxt=-1;
for(int j=0 ; j<n ; j++) {
if(used[j]) continue;
if(nxt==-1||cmp(split[j][i],split[nxt][i])) nxt=j;
}
used[nxt]=1;
ans.push_back(split[nxt][i]);
p[i]=nxt;
}
ans.pop_back();
// the one with larger end will always fit in the next window
// so we can greedy choose the one with smallest split at i
for(frac tmp: ans) cout<<tmp.who*tmp.den+tmp.num<<' '<<tmp.den<<'\n';
for(int i=0 ; i<n ; i++) cout<<p[i]+1<<' ';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
0 ms |
276 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
2 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
1 ms |
460 KB |
Output is correct |
| 10 |
Correct |
2 ms |
460 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| 15 |
Correct |
1 ms |
460 KB |
Output is correct |
| 16 |
Correct |
1 ms |
460 KB |
Output is correct |
| 17 |
Correct |
1 ms |
460 KB |
Output is correct |
| 18 |
Correct |
1 ms |
460 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
2 ms |
460 KB |
Output is correct |
| 22 |
Correct |
1 ms |
460 KB |
Output is correct |
| 23 |
Correct |
0 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
332 KB |
Output is correct |
| 25 |
Correct |
1 ms |
332 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
332 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
0 ms |
276 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
332 KB |
Output is correct |
| 9 |
Correct |
0 ms |
332 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Correct |
1 ms |
332 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
332 KB |
Output is correct |
| 14 |
Correct |
1 ms |
332 KB |
Output is correct |
| 15 |
Correct |
2 ms |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
332 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
1 ms |
332 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
460 KB |
Output is correct |
| 25 |
Correct |
2 ms |
460 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
460 KB |
Output is correct |
| 30 |
Correct |
1 ms |
460 KB |
Output is correct |
| 31 |
Correct |
1 ms |
460 KB |
Output is correct |
| 32 |
Correct |
1 ms |
460 KB |
Output is correct |
| 33 |
Correct |
1 ms |
460 KB |
Output is correct |
| 34 |
Correct |
1 ms |
460 KB |
Output is correct |
| 35 |
Correct |
1 ms |
332 KB |
Output is correct |
| 36 |
Correct |
2 ms |
460 KB |
Output is correct |
| 37 |
Correct |
1 ms |
460 KB |
Output is correct |
| 38 |
Correct |
0 ms |
332 KB |
Output is correct |
| 39 |
Correct |
1 ms |
332 KB |
Output is correct |
| 40 |
Correct |
1 ms |
332 KB |
Output is correct |
| 41 |
Correct |
1 ms |
332 KB |
Output is correct |
| 42 |
Correct |
1 ms |
332 KB |
Output is correct |
| 43 |
Correct |
59 ms |
14428 KB |
Output is correct |
| 44 |
Correct |
365 ms |
78528 KB |
Output is correct |
| 45 |
Correct |
161 ms |
32524 KB |
Output is correct |
| 46 |
Correct |
16 ms |
3700 KB |
Output is correct |
| 47 |
Correct |
216 ms |
47272 KB |
Output is correct |
| 48 |
Correct |
449 ms |
106516 KB |
Output is correct |
| 49 |
Correct |
109 ms |
29768 KB |
Output is correct |
| 50 |
Correct |
592 ms |
128612 KB |
Output is correct |
| 51 |
Correct |
210 ms |
50300 KB |
Output is correct |
| 52 |
Correct |
485 ms |
110076 KB |
Output is correct |
| 53 |
Correct |
426 ms |
103236 KB |
Output is correct |
| 54 |
Correct |
1 ms |
332 KB |
Output is correct |
| 55 |
Correct |
230 ms |
59560 KB |
Output is correct |
| 56 |
Correct |
301 ms |
69700 KB |
Output is correct |
| 57 |
Correct |
227 ms |
60740 KB |
Output is correct |
| 58 |
Correct |
410 ms |
101568 KB |
Output is correct |
| 59 |
Correct |
241 ms |
56044 KB |
Output is correct |
| 60 |
Correct |
597 ms |
149880 KB |
Output is correct |
| 61 |
Correct |
618 ms |
150124 KB |
Output is correct |
| 62 |
Correct |
675 ms |
149620 KB |
Output is correct |
| 63 |
Correct |
681 ms |
150160 KB |
Output is correct |
| 64 |
Correct |
601 ms |
149972 KB |
Output is correct |
| 65 |
Correct |
646 ms |
136656 KB |
Output is correct |
| 66 |
Correct |
636 ms |
136748 KB |
Output is correct |
| 67 |
Correct |
562 ms |
136824 KB |
Output is correct |
| 68 |
Correct |
243 ms |
75200 KB |
Output is correct |
| 69 |
Correct |
237 ms |
68712 KB |
Output is correct |
| 70 |
Correct |
312 ms |
91584 KB |
Output is correct |
| 71 |
Correct |
388 ms |
102092 KB |
Output is correct |
