| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 310015 |
2020-10-05T10:24:40 Z |
YJU |
Naan (JOI19_naan) |
C++14 |
|
727 ms |
85508 KB |
#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-')w=0,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
#define ll long long
#define pi pair<ll,ll>
#define mk make_pair
#define fi first
#define se second
const int N=2005;
pi p[N][N],ans1[N];int n,m,val[N],vis[N],ans2[N];
bool cmp(pi a,pi b){return (long double)a.fi/a.se<(long double)b.fi/b.se;}
int main(){
n=gi();m=gi();
for(int i=1;i<=n;++i){
ll sum=0,now=0;
for(int j=1;j<=m;++j)sum+=(val[j]=gi());
for(int j=1,k=1;j<=n;++j){
while(k<m&&(now+val[k])*n<sum*j)now+=val[k++];
ll a=1ll*n*val[k]*(k-1)+sum*j-now*n,b=1ll*n*val[k],d=__gcd(a,b);
p[i][j]=mk(a/d,b/d);
}
}
for(int i=1;i<=n;++i){
int x=0;p[x][i]=mk(1,0);
for(int j=1;j<=n;++j)if(!vis[j])x=cmp(p[j][i],p[x][i])?j:x;
ans1[i]=p[x][i];ans2[i]=x;vis[x]=1;
}
for(int i=1;i<n;++i)printf("%lld %lld\n",ans1[i].fi,ans1[i].se);
for(int i=1;i<=n;++i)printf("%d ",ans2[i]);return puts(""),0;
}
Compilation message
naan.cpp: In function 'int main()':
naan.cpp:36:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
36 | for(int i=1;i<=n;++i)printf("%d ",ans2[i]);return puts(""),0;
| ^~~
naan.cpp:36:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
36 | for(int i=1;i<=n;++i)printf("%d ",ans2[i]);return puts(""),0;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
1 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
0 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
416 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
372 KB |
Output is correct |
| 23 |
Correct |
0 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
384 KB |
Output is correct |
| 27 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
1 ms |
384 KB |
Output is correct |
| 8 |
Correct |
1 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
384 KB |
Output is correct |
| 10 |
Correct |
1 ms |
384 KB |
Output is correct |
| 11 |
Correct |
1 ms |
384 KB |
Output is correct |
| 12 |
Correct |
1 ms |
384 KB |
Output is correct |
| 13 |
Correct |
1 ms |
384 KB |
Output is correct |
| 14 |
Correct |
1 ms |
384 KB |
Output is correct |
| 15 |
Correct |
1 ms |
384 KB |
Output is correct |
| 16 |
Correct |
1 ms |
384 KB |
Output is correct |
| 17 |
Correct |
1 ms |
384 KB |
Output is correct |
| 18 |
Correct |
1 ms |
384 KB |
Output is correct |
| 19 |
Correct |
1 ms |
384 KB |
Output is correct |
| 20 |
Correct |
1 ms |
384 KB |
Output is correct |
| 21 |
Correct |
1 ms |
384 KB |
Output is correct |
| 22 |
Correct |
1 ms |
384 KB |
Output is correct |
| 23 |
Correct |
1 ms |
384 KB |
Output is correct |
| 24 |
Correct |
1 ms |
384 KB |
Output is correct |
| 25 |
Correct |
1 ms |
384 KB |
Output is correct |
| 26 |
Correct |
1 ms |
384 KB |
Output is correct |
| 27 |
Correct |
0 ms |
384 KB |
Output is correct |
| 28 |
Correct |
1 ms |
384 KB |
Output is correct |
| 29 |
Correct |
1 ms |
384 KB |
Output is correct |
| 30 |
Correct |
1 ms |
384 KB |
Output is correct |
| 31 |
Correct |
1 ms |
384 KB |
Output is correct |
| 32 |
Correct |
1 ms |
384 KB |
Output is correct |
| 33 |
Correct |
1 ms |
416 KB |
Output is correct |
| 34 |
Correct |
1 ms |
384 KB |
Output is correct |
| 35 |
Correct |
1 ms |
384 KB |
Output is correct |
| 36 |
Correct |
1 ms |
384 KB |
Output is correct |
| 37 |
Correct |
1 ms |
372 KB |
Output is correct |
| 38 |
Correct |
0 ms |
384 KB |
Output is correct |
| 39 |
Correct |
1 ms |
384 KB |
Output is correct |
| 40 |
Correct |
1 ms |
384 KB |
Output is correct |
| 41 |
Correct |
1 ms |
384 KB |
Output is correct |
| 42 |
Correct |
1 ms |
384 KB |
Output is correct |
| 43 |
Correct |
61 ms |
9168 KB |
Output is correct |
| 44 |
Correct |
374 ms |
45176 KB |
Output is correct |
| 45 |
Correct |
153 ms |
18040 KB |
Output is correct |
| 46 |
Correct |
17 ms |
2176 KB |
Output is correct |
| 47 |
Correct |
231 ms |
27592 KB |
Output is correct |
| 48 |
Correct |
502 ms |
61048 KB |
Output is correct |
| 49 |
Correct |
108 ms |
16740 KB |
Output is correct |
| 50 |
Correct |
597 ms |
67832 KB |
Output is correct |
| 51 |
Correct |
197 ms |
25336 KB |
Output is correct |
| 52 |
Correct |
490 ms |
60152 KB |
Output is correct |
| 53 |
Correct |
450 ms |
56568 KB |
Output is correct |
| 54 |
Correct |
1 ms |
384 KB |
Output is correct |
| 55 |
Correct |
245 ms |
37240 KB |
Output is correct |
| 56 |
Correct |
271 ms |
36088 KB |
Output is correct |
| 57 |
Correct |
224 ms |
31352 KB |
Output is correct |
| 58 |
Correct |
416 ms |
56440 KB |
Output is correct |
| 59 |
Correct |
216 ms |
28664 KB |
Output is correct |
| 60 |
Correct |
654 ms |
85112 KB |
Output is correct |
| 61 |
Correct |
664 ms |
85112 KB |
Output is correct |
| 62 |
Correct |
727 ms |
84952 KB |
Output is correct |
| 63 |
Correct |
691 ms |
85508 KB |
Output is correct |
| 64 |
Correct |
679 ms |
85276 KB |
Output is correct |
| 65 |
Correct |
647 ms |
72056 KB |
Output is correct |
| 66 |
Correct |
646 ms |
72056 KB |
Output is correct |
| 67 |
Correct |
567 ms |
72056 KB |
Output is correct |
| 68 |
Correct |
250 ms |
41848 KB |
Output is correct |
| 69 |
Correct |
237 ms |
37112 KB |
Output is correct |
| 70 |
Correct |
310 ms |
51832 KB |
Output is correct |
| 71 |
Correct |
379 ms |
57336 KB |
Output is correct |
