Submission #131827

#	Time	Username	Problem	Language	Result	Execution time	Memory
131827		SirCeness	Naan (JOI19_naan)	C++14	100 / 100	919 ms	125896 KiB

naan

#include <bits/stdc++.h>
 
using namespace std;
#define mod 998244353
#define mp make_pair
#define pb push_back
#define bas(x) #x << ": " << x << " "
#define prarr(x, n) cout << #x << ": "; for (int qsd = 0; qsd < n; qsd++) cout << x[qsd] << " "; cout << endl;
#define prarrv(x) cout << #x << ": "; for (int qsd = 0; qsd < (int)x.size(); qsd++) cout << x[qsd] << " "; cout << endl;
#define inside sl<=l%&&r<=sr
#define outside sr<l||r<sl

typedef long long ll;

int n, m;
ll mat[2002][2002];
ll presum[2002][2002];
pair<ll, ll> bol[2002][2002];

vector<pair<ll, ll> > ans;
vector<int> p;
 
pair<ll, ll> sum(pair<ll, ll> a, pair<ll, ll> b){
	ll pay = a.first*b.second + a.second*b.first;
	ll payda = a.second*b.second;
	return mp(pay, payda);
}
 
 
pair<ll, ll> get(int i, ll pay, ll payda){
	cout << "get(" << i << ", " << pay << ", "  << payda << ")" << endl;
	/*double ans = presum[i][(int)(pay/payda)-1];
	ans += mat[i][(int)(pay/payda)]*((pay/payda) - (int)(pay/payda));
	return ans;*/
	return sum(mp(presum[i][(pay/payda)-1], 1), mp((pay%payda)*mat[i][pay/payda], payda));
}

pair<ll, ll> getmin(int i, pair<ll, ll> puan){
	//cout << "getmin(" << i << ", " << puan.first << ", " << puan.second << ")" << endl;
	if (presum[i][m-1] < (double)puan.first/(double)puan.second) return mp(-1, -1);
	int l = -1;
	int r = m-1;
	while (l < r){
		int m = (l+r+1)/2;
		if (presum[i][m] > (double)puan.first/(double)puan.second) r = m-1;
		else l = m;
	}
	//cout << bas(l) << endl;
	if (l != -1 && presum[i][l] == (double)puan.first/(double)puan.second) return mp(l+1, 1);
	puan = sum(puan, mp((l == -1) ? 0 : -presum[i][l], 1));
	// mat[i][l+1]*oran = puan;
	return sum(mp(l+1, 1), mp(puan.first, puan.second*mat[i][l+1]));
}

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n; i++){
		ll cur = 0;
		for (int j = 0; j < m; j++){
			cin >> mat[i][j];
			cur += mat[i][j];
			presum[i][j] = cur;
		}
	}
	
	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			bol[j][i] = getmin(i, mp(presum[i][m-1]*(j+1), n)); 
			//cout << bol[i][j].first << ", " << bol[i][j].second  << " ";
		}
		//cout << endl;
	}
	//cout << endl;
	
	bitset<2002> vis;
	vis.reset();
	for (int i = 0; i < n; i++){
		double minn = 1000000000;
		int mini = -1;
		for (int j = 0; j < n; j++){
			if (vis[j]) continue;
			//cout << bas(i) << " " bas(j) << endl;
			//cout << bas(minn) << " " << bas(bol[i][j].first) << bas(bol[i][j].second) << endl;
 			if ((double)bol[i][j].first / (double)bol[i][j].second < minn){
				minn = (double)bol[i][j].first / (double)bol[i][j].second;
				mini = j;
			}
		}
		ans.pb(bol[i][mini]);
		p.pb(mini+1);
		vis[mini] = 1;
	}
	
	for (int i = 0; i < n-1; i++) cout << ans[i].first << " " << ans[i].second << endl;
	
	for (int i = 0; i < p.size(); i++) cout << p[i] << " ";
	
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++) cout << p[i] << " ";
                  ~~^~~~~~~~~~

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