제출 #1016342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1016342		mofumofu	Naan (JOI19_naan)	C++17	29 / 100	121 ms	56656 KiB

naan

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
//#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ti tuple<ll,ll,ll>
#define vi vector<int>
#define ff first 
#define ss second
#define rep(i,a,b) for(ll i=(a); i<(b); i++)
#define repd(i,a,b) for(ll i=(a)-1; i!=(b)-1; i--)
#define all(x) x.begin(),x.end()
#define sz(a) ((int) (a).size())
#define me(a, x) memset(a, x, sizeof(a))
#define nl '\n'
#define cma <<','<<
ll mod = 998244353;
ll inf = 1e18;
const int maxn = 1e5+5;
const ll lg = 20;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//uniform_int_distribution<> dist(1, 2);
inline ld gen_random(ld l, ld r) {
    return uniform_real_distribution<ld>(l, r)(rng);
}

pll reduce(pll a){
	ll g = __gcd(a.ff, a.ss);
	pll b = {a.ff / g, a.ss / g};
	return b;
}

bool cmp(pll &a, pll &b){
	return a.ff * b.ss < a.ss * b.ff;
}


int main() {
    ios::sync_with_stdio(0);
	cin.tie(0);
	 
	int n,l; cin >> n >> l;
	
	vector v(n, vector<ll>(l));
	vector s(n, vector<ll>(l));
	rep(i,0,n){
		rep(j,0,l){
			cin >> v[i][j];
			v[i][j] *= n;
			s[i][j] = (j > 0 ? s[i][j - 1] : 0) + v[i][j];
		}
	}
	
	vector div(n, vector<pll>(n));
	rep(i,0,n){
		ll sum = accumulate(all(v[i]), 0LL);
		ll portion = sum / n;
		
		ll cur = 1;
		rep(j,0,l){
			while(cur * portion < s[i][j]){
				ll prev = (j > 0 ? s[i][j - 1] : 0);
				ll leftover = cur * portion - prev;
				
				div[i][cur - 1] = {j * v[i][j] + leftover, v[i][j]};
				cur++;
			}
		}
	}
	
	vector<int> used(n);
	vector<int> ans;
	
	rep(i, 0, n - 1){
		vector<pair<pll, int>> f;
		pll best = {l, 1};
		int id = -1;
		rep(j, 0, n){
			if(!used[j]){
				pll a = div[j][i];
				if(cmp(a, best)){
					best = a;
					id = j;
				}
			}
		}
		cout << best.ff << " " << best.ss << nl;
		ans.pb(id);
		used[id] = 1;
	}
	
	rep(i,0,n){
		if(!used[i]) ans.pb(i);
	}
	
	for(auto i: ans){
		cout << i + 1 << " ";
	}
	
	
	
	
	
}

/*



*/

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