oj.uz

답안 #445168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
445168 2021-07-16T17:27:32 Z Jasiekstrz Naan (JOI19_naan) C++17
100 / 100
 481 ms 85440 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);
	return Quo(a.x*b.y+b.x*a.y,a.y*b.y);
}
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 (__int128)a.x*b.y<(__int128)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(pref[i][it[i]+1]*n<pref[i][l]*k)
				it[i]++;
			//Quo xd=read(i,Quo(it[i],1));
			//xd.norm();
			Quo tmp=Quo(it[i],1)+(Quo(pref[i][l]*k,n)-Quo(pref[i][it[i]],1))*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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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

# 결과 실행 시간 메모리 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 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 1 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 1 ms 460 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 460 KB Output is correct
21 Correct 1 ms 460 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 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 1 ms 460 KB Output is correct

Subtask #3
71.0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 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 1 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 1 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 1 ms 460 KB Output is correct
33 Correct 1 ms 460 KB Output is correct
34 Correct 1 ms 460 KB Output is correct
35 Correct 1 ms 460 KB Output is correct
36 Correct 1 ms 460 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 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 1 ms 460 KB Output is correct
43 Correct 33 ms 8952 KB Output is correct
44 Correct 215 ms 38256 KB Output is correct
45 Correct 143 ms 29476 KB Output is correct
46 Correct 22 ms 5176 KB Output is correct
47 Correct 169 ms 38336 KB Output is correct
48 Correct 123 ms 30588 KB Output is correct
49 Correct 52 ms 16324 KB Output is correct
50 Correct 274 ms 61636 KB Output is correct
51 Correct 158 ms 36768 KB Output is correct
52 Correct 313 ms 61288 KB Output is correct
53 Correct 230 ms 54212 KB Output is correct
54 Correct 1 ms 404 KB Output is correct
55 Correct 41 ms 14344 KB Output is correct
56 Correct 201 ms 45300 KB Output is correct
57 Correct 164 ms 39748 KB Output is correct
58 Correct 204 ms 48708 KB Output is correct
59 Correct 191 ms 39620 KB Output is correct
60 Correct 470 ms 85204 KB Output is correct
61 Correct 479 ms 85240 KB Output is correct
62 Correct 481 ms 85064 KB Output is correct
63 Correct 471 ms 85440 KB Output is correct
64 Correct 470 ms 85316 KB Output is correct
65 Correct 386 ms 72000 KB Output is correct
66 Correct 376 ms 72064 KB Output is correct
67 Correct 387 ms 71928 KB Output is correct
68 Correct 183 ms 43024 KB Output is correct
69 Correct 221 ms 47064 KB Output is correct
70 Correct 200 ms 47248 KB Output is correct
71 Correct 308 ms 61380 KB Output is correct