oj.uz

Submission #533319

# Submission time Handle Problem Language Result Execution time Memory
533319 2022-03-05T12:49:18 Z codr0 Naan (JOI19_naan) C++14
29 / 100
 4000 ms 42932 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){
		int gc=__gcd(X.F,X.S);
		X.S/=gc;
		X.F/=gc;
		return X;
	}

	pii sum(pii a,pii b){// a+b
		a=simp(a);
		b=simp(b);
		pii rt;
		int gc=__gcd(a.S,b.S);
		rt.S=a.S*b.S/gc;
		rt.F=a.F*(b.S/gc)+b.F*(a.S/gc);
		rt=simp(rt);
		return rt;
	}

	pii mul(pii a,pii b){// a*b
		a=simp(a);
		b=simp(b);
		pii rt;
		rt.F=a.F*b.F;
		rt.S=a.S*b.S;
		rt=simp(rt);
		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
		a=simp(a);
		b=simp(b);
		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:108:2: note: in expansion of macro 'FOR'
  108 |  FOR(i,1,n) cout<<p[i]<<" "; cout<<'\n';
      |  ^~~
naan.cpp:108:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |  FOR(i,1,n) cout<<p[i]<<" "; cout<<'\n';
      |                              ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 280 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 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 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 5 ms 332 KB Output is correct
5 Correct 4 ms 332 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 6 ms 408 KB Output is correct
10 Correct 5 ms 332 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 3 ms 364 KB Output is correct
14 Correct 6 ms 332 KB Output is correct
15 Correct 5 ms 332 KB Output is correct
16 Correct 5 ms 332 KB Output is correct
17 Correct 5 ms 332 KB Output is correct
18 Correct 5 ms 332 KB Output is correct
19 Correct 5 ms 332 KB Output is correct
20 Correct 5 ms 400 KB Output is correct
21 Correct 5 ms 332 KB Output is correct
22 Correct 5 ms 412 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 4 ms 332 KB Output is correct
25 Correct 3 ms 376 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 5 ms 392 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 280 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 1 ms 332 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 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 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 2 ms 332 KB Output is correct
18 Correct 3 ms 332 KB Output is correct
19 Correct 5 ms 332 KB Output is correct
20 Correct 4 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 6 ms 408 KB Output is correct
25 Correct 5 ms 332 KB Output is correct
26 Correct 4 ms 332 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 3 ms 364 KB Output is correct
29 Correct 6 ms 332 KB Output is correct
30 Correct 5 ms 332 KB Output is correct
31 Correct 5 ms 332 KB Output is correct
32 Correct 5 ms 332 KB Output is correct
33 Correct 5 ms 332 KB Output is correct
34 Correct 5 ms 332 KB Output is correct
35 Correct 5 ms 400 KB Output is correct
36 Correct 5 ms 332 KB Output is correct
37 Correct 5 ms 412 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 4 ms 332 KB Output is correct
40 Correct 3 ms 376 KB Output is correct
41 Correct 1 ms 332 KB Output is correct
42 Correct 5 ms 392 KB Output is correct
43 Correct 854 ms 7336 KB Output is correct
44 Execution timed out 4096 ms 42932 KB Time limit exceeded
45 Halted 0 ms 0 KB -