Submission #131829

#	Time	Username	Problem	Language	Result	Execution time	Memory
131829		ekrem	Naan (JOI19_naan)	C++98	100 / 100	2575 ms	188920 KiB

naan

#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 2005
using namespace std;

typedef long long ll;
typedef pair < ll , ll > ii;

ll n, m, bul, top[N], ans[N], u[N], a[N][N], pre[N][N];
pair < double , ll > b[N][N];
ii c[N][N];

ll gcd(ll x, ll y){
	if(!x or !y)
		return x + y;
	return gcd(y%x, x);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%lld %lld",&n ,&m);
	for(ll i = 1; i <= n; i++)
		for(ll j = 1; j <= m; j++){
			scanf("%lld",&a[i][j]);
			top[i] += a[i][j];
			a[i][j] *= n;
			pre[i][j] = pre[i][j - 1] + a[i][j];
		}
	for(ll i = 1; i < n; i++){
		for(ll j = 1; j <= n; j++){
			bul = top[j]*i;
			ll ind = upper_bound(pre[j] + 1, pre[j] + m + 1, bul) - pre[j] - 1;
			// cout << j << " " << i << " " <<bul << " " << ind << " " << pre[j][ind] << endl;
			bul -= pre[j][ind];
			ll x = ind*a[j][ind + 1] + bul;
			ll y = a[j][ind + 1];
			ll gg = gcd(x, y);
			x /= gg;y /= gg;
			// cout << x << " " << y << endl;
			b[i][j] = mp(1.0*x/y, j);
			c[i][j] = mp(x, y);
		}
		sort(b[i] + 1, b[i] + n + 1);
	}
	for(ll i = 1; i <= n; i++)
		b[n][i] = mp(0.0, i);
	for(ll i = 1; i <= n; i++){
		for(ll j = 1; j <= n; j++){
			if(!u[b[i][j].nd]){
				ans[i] = b[i][j].nd;
				u[ans[i]] = 1;
				if(i != n)
					printf("%lld %lld\n", c[i][ans[i]].st, c[i][ans[i]].nd);
				break;
			}
		}
	}
	for(ll i = 1; i <= n; i++)
		printf("%lld ", ans[i]);
	return 0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n ,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
naan.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&a[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~

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