Submission #378052

#	Time	Username	Problem	Language	Result	Execution time	Memory
378052		pit4h	Naan (JOI19_naan)	C++14	0 / 100	1 ms	364 KiB

naan

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
using ld = long double;
const int MAXN = 2e3+1;
const ll inf = 1e9, INF = 1e12;
int n, l, v[MAXN][MAXN], pref[MAXN][MAXN];

ll round(ll p, ll q) {
	ll lo = 0, hi = INF, res=0;
	while(lo<=hi) {
		ll mid = (lo+hi)/2;
		if((ld)mid/inf >= (ld)p/q) {
			res = mid;
			hi = mid-1;
		}
		else {
			lo = mid+1;
		}
	}
	return res;
}

ll calc(ll start, int it) {
	int st = start / inf;
	int lo = st, hi = l-1, res=st;
	ll beg = v[it][st] * ((st+1)*inf - start);
	//cerr<<"  "<<beg.p<<' '<<beg.q<<'\n';
	ll score = 0, lim = round(pref[it][l], n); 
	while(lo <= hi) {
		int mid = (lo+hi)/2;
		ll cur_score = beg + (pref[it][mid] - pref[it][st]) * inf;
		//cerr<<"  "<<mid<<": "<<cur_score.p<<' '<<cur_score.q<<'\n';
		if(cur_score <= lim) {
			//cerr<<".\n";
			score = cur_score;
			res = mid + 1;
			lo = mid+1;
		}
		else {
			hi = mid-1;
		}
	}
	//cerr<<"  "<<st<<' '<<res<<' '<<score.p<<' '<<score.q<<'\n';
	ll ret;
	if(res>st) {
		ret = res * inf + round((round(pref[it][l], n) - score), v[it][res] * inf);
	}
	else {
		ret = start + round((round(pref[it][l], n) - score), v[it][res] * inf);
	}
	return ret;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>l;
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=l; ++j) {
			cin>>v[i][j];
			pref[i][j] = pref[i][j-1] + v[i][j];
		}
	}
	vector<int> people;
	for(int i=1; i<=n; ++i) people.push_back(i);

	ll start = 1;
	vector<int> perm;
	vector<ll> X;
	for(int iter=1; iter<=n; ++iter) {
		int& best = people[0];
		ll bestv;
		//cerr<<"iter: "<<iter<<'\n';
		for(int& i: people) {
			//cerr<<i<<'\n';
			ll curv = calc(start, i);
			//cerr<<' '<<curv.p<<' '<<curv.q<<'\n';
			if(i==people[0] || curv < bestv) {
				swap(best, i);
				bestv = curv;
			}
		}
		perm.push_back(best);

		start = bestv;
		best = people.back();
		people.pop_back();
		
		if(iter < n) X.push_back(start);
	}

	for(auto& i: X) {
		i = i - inf;
		cout<<i<<' '<<inf<<'\n';	
	}
	for(auto i: perm) {
		cout<<i<<' ';
	}
	cout<<'\n';
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:80:20: warning: 'bestv' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |    if(i==people[0] || curv < bestv) {
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~

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