Submission #412474

#	Time	Username	Problem	Language	Result	Execution time	Memory
412474		rqi	Naan (JOI19_naan)	C++14	29 / 100	4074 ms	179356 KiB

naan

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

typedef vector<int> vi;
typedef __int128 ll;

#define pb push_back

const int MOD = 1e9+7;
const int mx = 2005;


ll ABS(ll a){
	if(a < 0) return -a;
	return a;
}

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){
		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){
	return frac(a.n*b.d, a.d*b.n);
}

void print(frac a){
	cout << (int)(a.n) << "/" << (int)(a.d) << " ";
}

bool isEqual(frac a, frac b){
	return a.n*b.d == b.n*a.d;
}

bool isLess(frac a, frac b){
	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;
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= L; j++){
			int val;
			cin >> val;
			V[i][j] = val;
		}
	}

	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
		frac cur_happy = frac(0);
		for(int j = 1; j <= N; j++){
			//cout << "j: " << j << "\n";
			while(cur_eaten+1 <= L){

				if(isLess(cur_happy+frac(V[i][cur_eaten+1], weight_sum), frac(j, N))){
					cur_happy+=frac(V[i][cur_eaten+1], weight_sum);
					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)+(frac(j, N)-cur_happy)/(frac(V[i][cur_eaten+1], weight_sum));
		}
	}

	// 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 << (long long)(earliest.n) << " " << int(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;
			}
		}
	}

	for(auto u: perm){
		cout << u << " ";
	}
	cout << "\n";
}

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