oj.uz

Submission #445164

# Submission time Handle Problem Language Result Execution time Memory
445164 2021-07-16T17:17:57 Z Jasiekstrz Naan (JOI19_naan) C++17
29 / 100
 321 ms 38148 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e3;
struct Quo
{
	long long x,y;
	Quo(long long _x=0,long long _y=1) : x(_x),y(_y) {};
	void norm()
	{
		long long c=gcd(x,y);
		x/=c;
		y/=c;
		return;
	}
};
Quo operator+(Quo a,Quo b)
{
	long long c=lcm(a.y,b.y);
	return Quo(a.x*(c/a.y)+b.x*(c/b.y),c);
}
Quo operator-(Quo a,Quo b)
{
	b.x=-b.x;
	return a+b;
}
Quo operator*(Quo a,Quo b)
{
	return Quo(a.x*b.x,a.y*b.y);
}
bool operator<(Quo a,Quo b)
{
	return a.x*b.y<b.x*a.y;
}
long long tab[N+10][N+10];
long long pref[N+10][N+10];
int it[N+10];
bool vis[N+10];
Quo ans[N+10];
int per[N+10];
Quo read(int i,Quo c)
{
	return Quo(pref[i][c.x/c.y],1)+Quo(tab[i][c.x/c.y+1]*(c.x%c.y),c.y);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,l;
	cin>>n>>l;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=l;j++)
		{
			cin>>tab[i][j];
			pref[i][j]=pref[i][j-1]+tab[i][j];
		}
	}
	ans[0]=Quo(0,1);
	for(int k=1;k<=n;k++)
	{
		Quo bst=Quo(l+1,1);
		int g=0;
		for(int i=1;i<=n;i++)
		{
			if(vis[i])
				continue;
			while(read(i,Quo(it[i]+1,1))<Quo(pref[i][l]*k,n))
				it[i]++;
			Quo xd=read(i,Quo(it[i],1));
			xd.norm();
			Quo tmp=Quo(it[i],1)+(Quo(pref[i][l]*k,n)-xd)*Quo(1,tab[i][it[i]+1]);
			//cerr<<(Quo(pref[i][l],n)-xd).x<<" "<<(Quo(pref[i][l],n)-xd).y<<"\n";
			if(tmp<bst)
			{
				bst=tmp;
				g=i;
			}
		}
		//cerr<<g<<" "<<bst.x<<" "<<bst.y<<"\n";
		ans[k]=bst;
		per[k]=g;
		vis[g]=true;
	}
	for(int i=1;i<n;i++)
	{
		ans[i].norm();
		cout<<ans[i].x<<" "<<ans[i].y<<"\n";
	}
	for(int i=1;i<=n;i++)
		cout<<per[i]<<" \n"[i==n];
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 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

Subtask #2
24.0 / 24.0

# 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 2 ms 460 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 460 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 460 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 2 ms 460 KB Output is correct
18 Correct 2 ms 460 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 2 ms 460 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 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 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 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 2 ms 460 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 460 KB Output is correct
27 Correct 0 ms 332 KB Output is correct
28 Correct 1 ms 460 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 2 ms 460 KB Output is correct
33 Correct 2 ms 460 KB Output is correct
34 Correct 2 ms 460 KB Output is correct
35 Correct 1 ms 460 KB Output is correct
36 Correct 2 ms 460 KB Output is correct
37 Correct 1 ms 460 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 1 ms 460 KB Output is correct
40 Correct 1 ms 460 KB Output is correct
41 Correct 1 ms 332 KB Output is correct
42 Correct 2 ms 460 KB Output is correct
43 Correct 60 ms 8972 KB Output is correct
44 Incorrect 321 ms 38148 KB X_i is not increasing
45 Halted 0 ms 0 KB -