oj.uz

Submission #1016342

# Submission time Handle Problem Language Result Execution time Memory
1016342 2024-07-07T20:32:16 Z mofumofu Naan (JOI19_naan) C++17
29 / 100
 121 ms 56656 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
//#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ti tuple<ll,ll,ll>
#define vi vector<int>
#define ff first 
#define ss second
#define rep(i,a,b) for(ll i=(a); i<(b); i++)
#define repd(i,a,b) for(ll i=(a)-1; i!=(b)-1; i--)
#define all(x) x.begin(),x.end()
#define sz(a) ((int) (a).size())
#define me(a, x) memset(a, x, sizeof(a))
#define nl '\n'
#define cma <<','<<
ll mod = 998244353;
ll inf = 1e18;
const int maxn = 1e5+5;
const ll lg = 20;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//uniform_int_distribution<> dist(1, 2);
inline ld gen_random(ld l, ld r) {
    return uniform_real_distribution<ld>(l, r)(rng);
}

pll reduce(pll a){
	ll g = __gcd(a.ff, a.ss);
	pll b = {a.ff / g, a.ss / g};
	return b;
}

bool cmp(pll &a, pll &b){
	return a.ff * b.ss < a.ss * b.ff;
}


int main() {
    ios::sync_with_stdio(0);
	cin.tie(0);
	 
	int n,l; cin >> n >> l;
	
	vector v(n, vector<ll>(l));
	vector s(n, vector<ll>(l));
	rep(i,0,n){
		rep(j,0,l){
			cin >> v[i][j];
			v[i][j] *= n;
			s[i][j] = (j > 0 ? s[i][j - 1] : 0) + v[i][j];
		}
	}
	
	vector div(n, vector<pll>(n));
	rep(i,0,n){
		ll sum = accumulate(all(v[i]), 0LL);
		ll portion = sum / n;
		
		ll cur = 1;
		rep(j,0,l){
			while(cur * portion < s[i][j]){
				ll prev = (j > 0 ? s[i][j - 1] : 0);
				ll leftover = cur * portion - prev;
				
				div[i][cur - 1] = {j * v[i][j] + leftover, v[i][j]};
				cur++;
			}
		}
	}
	
	vector<int> used(n);
	vector<int> ans;
	
	rep(i, 0, n - 1){
		vector<pair<pll, int>> f;
		pll best = {l, 1};
		int id = -1;
		rep(j, 0, n){
			if(!used[j]){
				pll a = div[j][i];
				if(cmp(a, best)){
					best = a;
					id = j;
				}
			}
		}
		cout << best.ff << " " << best.ss << nl;
		ans.pb(id);
		used[id] = 1;
	}
	
	rep(i,0,n){
		if(!used[i]) ans.pb(i);
	}
	
	for(auto i: ans){
		cout << i + 1 << " ";
	}
	
	
	
	
	
}

/*



*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 1 ms 600 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 1 ms 604 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 1 ms 604 KB Output is correct
30 Correct 1 ms 604 KB Output is correct
31 Correct 1 ms 600 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 1 ms 600 KB Output is correct
34 Correct 1 ms 604 KB Output is correct
35 Correct 1 ms 604 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 604 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 604 KB Output is correct
40 Correct 1 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 18 ms 9564 KB Output is correct
44 Incorrect 121 ms 56656 KB X_i is not increasing
45 Halted 0 ms 0 KB -