Submission #412477

#	Time	Username	Problem	Language	Result	Execution time	Memory
412477		rqi	Naan (JOI19_naan)	C++14	100 / 100	1372 ms	106812 KiB

naan

#include <bits/stdc++.h>
using namespace std;
 
typedef vector<int> vi;
typedef long long ll;
typedef long double db;
 
#define pb push_back
 
const int MOD = 1e9+7;
const int mx = 2005;
 
 
ll GCD(ll a, ll b){
	a = abs(a); b = abs(b);
	if(a == 0) return b;
	if(b == 0) return a;
	return GCD(b%a, a);
}
 
struct frac{
	ll n, d;
	frac(){
		n = 0;
		d = 1;
	}
	frac(ll _n, ll _d, bool mode){
		n = _n;
		d = _d;
	}
	frac(ll _n, ll _d){
		if(_d < 0){
			_n*=-1;
			_d*=-1;
		}
		assert(_d >= 1);
		ll g = GCD(_n, _d);
		n = _n/g;
		d = _d/g;
	}
	frac(ll _n){
		n = _n;
		d = 1;
	}
};
 
frac operator+(frac a, frac b){
	return frac(a.n*b.d+b.n*a.d, a.d*b.d);
}
 
frac& operator+=(frac& a, frac b){
	a = a+b;
	return a;
}
 
frac operator-(frac a, frac b){
	b.n*=-1;
	return a+b;
}
 
frac operator/(frac a, frac b){
	ll g_n = GCD(a.n, b.n);
	a.n/=g_n;
	b.n/=g_n;
	ll g_d = GCD(a.d, b.d);
	a.d/=g_d;
	b.d/=g_d;
	return frac(a.n*b.d, a.d*b.n);
}
 
void print(frac a){
	cout << a.n << "/" << a.d << " ";
}
 
bool isEqual(frac a, frac b){
	ll g_n = GCD(a.n, b.n);
	a.n/=g_n;
	b.n/=g_n;
	ll g_d = GCD(a.d, b.d);
	a.d/=g_d;
	b.d/=g_d;
	return a.n*b.d == b.n*a.d;
}
 
bool isLess(frac a, frac b){
	ll g_n = GCD(a.n, b.n);
	a.n/=g_n;
	b.n/=g_n;
	ll g_d = GCD(a.d, b.d);
	a.d/=g_d;
	b.d/=g_d;
	return a.n*b.d < b.n*a.d;
}
 
int N, L;
ll V[mx][mx];
frac poses[mx][mx]; //person i, j/N fraction
bool used[mx];
 
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> L;
	// N = 2000;
	// L = 2000;
	mt19937 rng(127);
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= L; j++){
			cin >> V[i][j];
			//V[i][j] = 1 + rng() % 100000;
		}
	}

	clock_t BEG = clock();
 
	for(int i = 1; i <= N; i++){
		//cout << "i: " << i << "\n";
		ll weight_sum = 0;
		for(int j = 1; j <= L; j++){
			weight_sum+=V[i][j];
		}
		int cur_eaten = 0; //current prefix eaten
		ll cur_happy = 0;
		//frac cur_happy = frac(0);
		for(int j = 1; j <= N; j++){
			//cout << "j: " << j << "\n";
			while(cur_eaten+1 <= L){
 
				if(cur_happy+V[i][cur_eaten+1]*ll(N) < ll(j)*weight_sum){
					cur_happy+=V[i][cur_eaten+1]*ll(N);
					cur_eaten++;
					// cout << "cur_eaten: " << cur_eaten << "\n";
					// print(cur_happy);
					// cout << "\n";
				}
				else{
					break;
				}
			}
			assert(cur_eaten < L);
			poses[i][j] = frac(cur_eaten*V[i][cur_eaten+1]*ll(N)+ll(j)*weight_sum-cur_happy, V[i][cur_eaten+1]*ll(N));
			//poses[i][j] = frac(cur_eaten)+(ll(j)*weight_sum-cur_happy)/(frac(V[i][cur_eaten+1]*ll(N)));
		}
	}

	//cout << db(clock()-BEG)/db(CLOCKS_PER_SEC) << "\n";
 
	// for(int i = 1; i <= N; i++){
	// 	for(int j = 1; j <= N; j++){
	// 		cout << i << " " << j << " ";
	// 		print(poses[i][j]);
	// 		cout << "\n";
	// 	}
	// }
	vi perm;
	for(int i = 1; i <= N; i++){
		frac earliest = frac(MOD, 1);
		for(int j = 1; j <= N; j++){
			if(used[j]) continue; 
			if(isLess(poses[j][i], earliest)){
				earliest = poses[j][i];
			}
		}
		if(i <= N-1){
			cout << earliest.n << " " << earliest.d << "\n";
		}
		
		for(int j = 1; j <= N; j++){
			if(used[j]) continue; 
			if(isEqual(poses[j][i], earliest)){
				perm.pb(j);
				used[j] = 1;
				break;
			}
		}
	}

	//cout << db(clock()-BEG)/db(CLOCKS_PER_SEC) << "\n";
 
	for(auto u: perm){
		cout << u << " ";
	}
	cout << "\n";
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:113:10: warning: unused variable 'BEG' [-Wunused-variable]
  113 |  clock_t BEG = clock();
      |          ^~~

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