| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 522684 |
2022-02-05T11:39:58 Z |
phamhoanghiep |
Naan (JOI19_naan) |
C++14 |
|
57 ms |
15860 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 2;
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 |
372 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
360 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
368 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 |
368 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 |
1 ms |
396 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 |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
380 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 |
372 KB |
Output is correct |
| 9 |
Correct |
1 ms |
424 KB |
Output is correct |
| 10 |
Correct |
1 ms |
460 KB |
Output is correct |
| 11 |
Correct |
1 ms |
460 KB |
Output is correct |
| 12 |
Correct |
1 ms |
332 KB |
Output is correct |
| 13 |
Correct |
1 ms |
376 KB |
Output is correct |
| 14 |
Correct |
1 ms |
376 KB |
Output is correct |
| 15 |
Correct |
1 ms |
376 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 |
360 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
2 ms |
424 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
372 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
360 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
368 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 |
368 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 |
1 ms |
396 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 |
460 KB |
Output is correct |
| 19 |
Correct |
1 ms |
460 KB |
Output is correct |
| 20 |
Correct |
1 ms |
380 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 |
372 KB |
Output is correct |
| 24 |
Correct |
1 ms |
424 KB |
Output is correct |
| 25 |
Correct |
1 ms |
460 KB |
Output is correct |
| 26 |
Correct |
1 ms |
460 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
376 KB |
Output is correct |
| 29 |
Correct |
1 ms |
376 KB |
Output is correct |
| 30 |
Correct |
1 ms |
376 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 |
360 KB |
Output is correct |
| 34 |
Correct |
1 ms |
460 KB |
Output is correct |
| 35 |
Correct |
2 ms |
424 KB |
Output is correct |
| 36 |
Correct |
2 ms |
376 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 |
376 KB |
Output is correct |
| 41 |
Correct |
1 ms |
332 KB |
Output is correct |
| 42 |
Correct |
1 ms |
452 KB |
Output is correct |
| 43 |
Incorrect |
57 ms |
15860 KB |
X_i is not increasing |
| 44 |
Halted |
0 ms |
0 KB |
- |
