Submission #112561

#	Time	Username	Problem	Language	Result	Execution time	Memory
112561		reality	Naan (JOI19_naan)	C++17	100 / 100	1475 ms	25208 KiB

naan

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int s[2048][2048];
ll cnt[2048];
ll sum[2048];
ll gcd(ll a,ll b) {
	return !b ? a : gcd(b, a % b);
}
void Rel(ll &a,ll &b) {
	ll g = gcd(a,b);
	a /= g;
	b /= g;
}
int main(void) {
    int n,m;
    cin>>n>>m;
    for (int i = 1;i <= n;++i)
    	for (int j = 1;j <= m;++j)
    		cin>>s[i][j];
    for (int i = 1;i <= n;++i)
    	for (int j = 1;j <= m;++j)
    		sum[i] += s[i][j];
    vi p(n);
    for (int i = 0;i < n;++i)
    	p[i] = i + 1;
    vi Order;
    vector < pair < ll , ll > > Frac;
    for (int i = 1;i <= m;++i) {
    	ll A = n,B = 1;
    	while (!p.empty() && A > 0) {
    		sort(all(p),[&](int x,int y) {
    				const ll curx = (sum[x] - cnt[x]);
    				const ll cury = (sum[y] - cnt[y]);
    				return curx * s[y][i] > cury * s[x][i];
	    	});
			int Index = p.back();
			ll C = (sum[Index] - cnt[Index]);
			ll D = s[Index][i];
			if (C * B > A * D) {
				break;
			}
			p.pop_back();
			Order.pb(Index);
			ll New_A = (A * D - B * C) / B;
			ll New_B = D;
			A = New_A;
			B = New_B;
			Frac.pb(mp(i * B * n - A,B * n));
			for (int j = 1;j <= n;++j)
				cnt[j] = 0;
		}
    	for (int j = 1;j <= n;++j)
    		cnt[j] += A * s[j][i] / B;
    }
    Frac.pop_back();
    for (auto & it : Frac)
    	Rel(it.fi,it.se);
    for (auto it : Frac)
    	cout << it.fi << ' ' << it.se << '\n';
    for (int i = 0;i < n;++i)
    	cout << Order[i] << " \n"[i == n - 1];
    return 0;
}

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