Submission #492817

#	Time	Username	Problem	Language	Result	Execution time	Memory
492817		jiahng	Naan (JOI19_naan)	C++14	29 / 100	388 ms	15876 KiB

naan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int __int128
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
//~ #define lbd(x, y) lower_bound(all(x), y)
//~ #define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef pair <pi,int> pii;
typedef long double ld;
#define maxn 2010
#define INF (ll)1e18
int MOD;
int32_t N, L, A[maxn][maxn];
bool done[maxn];
struct frac{
	int a, b;
	frac(int _a,int _b){
		a = _a, b = _b;
		int x = __gcd(a,b); a /= x; b /= x;
	}
	frac operator+(frac y){
		return frac(y.a * b + y.b * a, y.b * b);
	}
	frac operator-(frac y){
		y.a *= -1;
		return *this + y;
	}
	frac operator/(int y){
		return frac(a, b * y);
	}
	frac operator*(int y){
		return frac(a*y,b);
	}
	frac operator*(frac y){
		return frac(a*y.a,b*y.b);
	}
	bool operator<(frac y){
		return (__int128) a * y.b < (__int128) b * y.a;
	}
};
vector <frac> B[maxn];

int32_t main(){
	fast;

	cin >> N >> L;
	FOR(i,1,N) FOR(j,1,L) cin >> A[i][j];
	
	FOR(i,1,N){
		int sm = accumulate(A[i]+1,A[i] + L + 1, 0LL);
		frac cur = frac(0, 1);
		FOR(j,1,L){
			frac k = frac(1, 1);
			while (!(cur + frac(A[i][j],1) * k < frac(sm, N))){
				B[i].pb(frac(j, 1) - k + (frac(sm,N) - cur) / A[i][j]);
				k = k - (frac(sm,N) - cur) / A[i][j];
				cur = frac(0,1);
			}
			cur = cur + frac(A[i][j], 1) * k;
		}
	}
	//~ FOR(i,1,N){
		//~ cout << "Person " << i << '\n';
		//~ aFOR(j,B[i]){
			//~ cout << j.a << ' ' << j.b << '\n';
		//~ }
	//~ }
	//~ return 0;
	vector <frac> ans; vector <int32_t> P;
	FOR(i,0,N-2){
		int nxt = -1; 
		FOR(j,1,N) if (!done[j] && (nxt == -1 || B[j][i] < B[nxt][i])) nxt = j;
		done[nxt] = 1;
		assert(nxt != -1 && i < B[nxt].size());
		ans.pb(B[nxt][i]);
		P.pb(nxt);
	}
	FOR(i,1,N) if (!done[i]) P.pb(i);
	aFOR(i,ans){
		cout << int32_t(i.a) << ' ' << int32_t(i.b) << '\n';
	}
	aFOR(i,P) cout << i << ' ';
	
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from naan.cpp:2:
naan.cpp: In function 'int32_t main()':
naan.cpp:86:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<frac>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   assert(nxt != -1 && i < B[nxt].size());
      |                       ~~^~~~~~~~~~~~~~~

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