Submission #524363

#	Time	Username	Problem	Language	Result	Execution time	Memory
524363		AmShZ	Naan (JOI19_naan)	C++11	100 / 100	360 ms	101092 KiB

naan

//khodaya khodet komak kon
# include <bits/stdc++.h>

using namespace std;

typedef long long                                        ll;
typedef long double                                      ld;
typedef pair <int, int>                                  pii;
typedef pair <pii, int>                                  ppi;
typedef pair <int, pii>                                  pip;
typedef pair <pii, pii>                                  ppp;
typedef pair <ll, ll>                                    pll;

# define A                                               first
# define B                                               second
# define endl                                            '\n'
# define sep                                             ' '
# define all(x)                                          x.begin(), x.end()
# define kill(x)                                         return cout << x << endl, 0
# define SZ(x)                                           int(x.size())
# define lc                                              id << 1
# define rc                                              id << 1 | 1
# define fast_io                                         ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);

ll power(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2, md) % md : power(a * a % md, b / 2, md) % md));}

const int xn = 2e3 + 10;
const int xm = - 20 + 10;
const int sq = 320;
const int inf = 1e9 + 10;
const ll INF = 1e18 + 10;
const ld eps = 1e-15;
const int mod = 998244353;
const int base = 257;

int n, L, a[xn][xn], P[xn];
pll b[xn][xn];
bool mark[xn];

bool cmp(pll x, pll y){
	ld X = ld(x.A) / ld(x.B);
	ld Y = ld(y.A) / ld(y.B);
	return X <= Y;
}

int main(){
	fast_io;

	cin >> n >> L;
	for (int i = 1; i <= n; ++ i){
		int sum = 0;
		for (int j = 1; j <= L; ++ j)
			cin >> a[i][j], sum += a[i][j];
		int ptr = 0, last = 0;
		for (int j = 1; j <= n; ++ j){
			int res = sum;
			while (res){
				if (a[i][ptr + 1] * n - last < res){
					res -= a[i][ptr + 1] * n - last;
					++ ptr, last = 0;
					continue;
				}
				last += res, res = 0;
				int magh = a[i][ptr + 1] * n;
				b[i][j] = {1ll * ptr * magh + last, magh};
				if (last == a[i][ptr + 1] * n)
					++ ptr, last = 0;
			}
		}
	}
	for (int i = 1; i <= n; ++ i){
		int ind = - 1;
		pll mn = {inf, 1};
		for (int j = 1; j <= n; ++ j)
			if (!mark[j] && cmp(b[j][i], mn))
				mn = b[j][i], ind = j;
		mark[ind] = true, P[i] = ind;
		if (i < n)
			cout << mn.A << sep << mn.B << endl;
	}
	for (int i = 1; i <= n; ++ i)
		cout << P[i] << sep;
	cout << endl;

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 71 / 71