| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 533324 |
2022-03-05T13:15:20 Z |
codr0 |
Naan (JOI19_naan) |
C++14 |
|
218 ms |
63828 KB |
// Code by Parsa Eslami
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
using namespace std;
pii simp(pii X){
return X;
int gc=__gcd(X.F,X.S);
X.S/=gc;
X.F/=gc;
return X;
}
pii sum(pii a,pii b){// a+b
pii rt;
int gc=1;
if(a.S==b.S) gc=a.S;
rt.S=a.S*(b.S/gc);
rt.F=a.F*(b.S/gc)+b.F*(a.S/gc);
return rt;
}
pii mul(pii a,pii b){// a*b
pii rt;
rt.F=a.F*b.F;
rt.S=a.S*b.S;
if(a.S%b.F==0){
rt.S/=b.F;
rt.F/=b.F;
}
if(b.S%a.F==0){
rt.S/=a.F;
rt.F/=a.F;
}
return rt;
}
pii L(pii a,pii b){// a-b
b.F=-b.F;
return sum(a,b);
}
pii div(pii a,pii b){// a/b
swap(b.F,b.S);
return mul(a,b);
}
bool cmp(pii a,pii b){// a<=b
int A=a.F/a.S;
int B=b.F/b.S;
if(A!=B) return (A<B);
a.F-=A*a.S;
b.F-=B*b.S;
return (a.F*b.S<=a.S*b.F);
}
int32_t main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n,l; cin>>n>>l;
int v[n+1][l+1];
FOR(i,1,n) FOR(j,1,l) cin>>v[i][j];
pii a[n][n];
FOR(i,1,n){
pii point={0,1};//
pii S={0,1};//
int ind=1;//
int Sp=0;
FOR(j,1,l) Sp+=v[i][j];
pii targ={Sp,n};
FOR(j,1,n-1){
while(1){
pii l=div(L(targ,S),{v[i][ind],1});
if(cmp(sum(l,point),{1,1})){
a[i][j]=sum({ind-1,1},sum(l,point));
point=sum(l,point);
S={0,1};
if(point.F==point.S){
ind++;
point={0,1};
}
break;
}else{
S=sum(S,mul(L({1,1},point),{v[i][ind],1}));
ind++; point={0,1};
}
}
}
}
bool mark[n+1]={};
int p[n+1]={};
FOR(i,1,n-1){
pair<pii,int> ans={{1e9,1},-1};
FOR(j,1,n) if(!mark[j]){
pair<pii,int> x0={a[j][i],j};
if(ans.S==-1||cmp(x0.F,ans.F)) ans=x0;
}
mark[ans.S]=1;
p[i]=ans.S;
cout<<ans.F.F<<" "<<ans.F.S<<'\n';
}
FOR(i,1,n) if(!mark[i]) p[n]=i;
FOR(i,1,n) cout<<p[i]<<" "; cout<<'\n';
return 0;
}
Compilation message
naan.cpp: In function 'int32_t main()':
naan.cpp:7:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
7 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
| ^~~
naan.cpp:115:2: note: in expansion of macro 'FOR'
115 | FOR(i,1,n) cout<<p[i]<<" "; cout<<'\n';
| ^~~
naan.cpp:115:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
115 | FOR(i,1,n) cout<<p[i]<<" "; cout<<'\n';
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
308 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 |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
1 ms |
316 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 |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 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 |
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 |
204 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 |
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 |
332 KB |
Output is correct |
| 20 |
Correct |
1 ms |
332 KB |
Output is correct |
| 21 |
Correct |
2 ms |
328 KB |
Output is correct |
| 22 |
Correct |
1 ms |
332 KB |
Output is correct |
| 23 |
Correct |
1 ms |
316 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 |
0 ms |
308 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 |
384 KB |
Output is correct |
| 5 |
Correct |
1 ms |
376 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
332 KB |
Output is correct |
| 8 |
Correct |
1 ms |
320 KB |
Output is correct |
| 9 |
Correct |
1 ms |
316 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 |
332 KB |
Output is correct |
| 16 |
Correct |
1 ms |
332 KB |
Output is correct |
| 17 |
Correct |
1 ms |
320 KB |
Output is correct |
| 18 |
Correct |
1 ms |
332 KB |
Output is correct |
| 19 |
Correct |
1 ms |
332 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 |
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 |
204 KB |
Output is correct |
| 28 |
Correct |
1 ms |
332 KB |
Output is correct |
| 29 |
Correct |
1 ms |
332 KB |
Output is correct |
| 30 |
Correct |
1 ms |
332 KB |
Output is correct |
| 31 |
Correct |
1 ms |
332 KB |
Output is correct |
| 32 |
Correct |
1 ms |
332 KB |
Output is correct |
| 33 |
Correct |
1 ms |
332 KB |
Output is correct |
| 34 |
Correct |
1 ms |
332 KB |
Output is correct |
| 35 |
Correct |
1 ms |
332 KB |
Output is correct |
| 36 |
Correct |
2 ms |
328 KB |
Output is correct |
| 37 |
Correct |
1 ms |
332 KB |
Output is correct |
| 38 |
Correct |
1 ms |
316 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 |
36 ms |
7828 KB |
Output is correct |
| 44 |
Correct |
218 ms |
43600 KB |
Output is correct |
| 45 |
Correct |
141 ms |
25252 KB |
Output is correct |
| 46 |
Correct |
21 ms |
3140 KB |
Output is correct |
| 47 |
Correct |
185 ms |
34548 KB |
Output is correct |
| 48 |
Correct |
146 ms |
63828 KB |
Output is correct |
| 49 |
Runtime error |
48 ms |
33300 KB |
Execution killed with signal 8 |
| 50 |
Halted |
0 ms |
0 KB |
- |
