Submission #589651

#	Time	Username	Problem	Language	Result	Execution time	Memory
589651		alireza_kaviani	Naan (JOI19_naan)	C++17	100 / 100	512 ms	116872 KiB

naan

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 2010;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

ll n , L , ans[MAXN] , mark[MAXN] , ps[MAXN] , V[MAXN][MAXN];
pll pos[MAXN][MAXN];

int cmp(pll A , pll B){
	if(A.X / A.Y != B.X / B.Y)	return A.X / A.Y < B.X / B.Y;
	A.X %= A.Y; B.X %= B.Y;
	return A.X * B.Y < A.Y * B.X;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> L;
	for(int i = 1 ; i <= n ; i++){
		ll sum = 0;
		for(int j = 1 ; j <= L ; j++){
			cin >> V[i][j];
			sum += V[i][j];
			ps[j] = ps[j - 1] + V[i][j] * n;
		}
		for(int j = 1 ; j <= n ; j++){
			int ind = lower_bound(ps , ps + L + 1 , sum * j) - ps;
			pos[i][j] = {sum * j - ps[ind - 1] + (ind - 1) * V[i][ind] * n , V[i][ind] * n};
			//cout << i << sep << j << sep << pos[i][j].X << sep << pos[i][j].Y << endl;
		}
	}
	for(int i = 1 ; i <= n ; i++){
		pll mn = {MOD , 1};
		for(int j = 1 ; j <= n ; j++){
			if(!mark[j]){
				if(cmp(pos[j][i] , mn)){
					mn = pos[j][i];
					ans[i] = j;
				}
			}
		}
		mark[ans[i]] = 1;
		if(i != n){
			cout << mn.X << sep << mn.Y << endl;
		}
	}
	for(int i = 1 ; i <= n ; i++){
		cout << ans[i] << sep;
	}

    return 0;
}
/*

*/

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