oj.uz

Submission #524404

# Submission time Handle Problem Language Result Execution time Memory
524404 2022-02-09T07:16:27 Z ymm Naan (JOI19_naan) C++17
29 / 100
 794 ms 13072 KB 
///
///   Oh? You're approaching me?
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for(ll x = ll(r)-1; x >= ll(l); --x)
#define Kill(x) exit((cout << (x) << '\n', 0))
typedef __int128 ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

struct frac{
	ll a, b;
	frac(){a=0;b=1;}
	frac(ll x){a=x;b=1;}
	frac(ll x, ll y){a=x;b=y;}
};
void gd(frac f){assert(f.a >= 0 && f.b > 0);}
frac red(frac f){ll g = f.a?__gcd(f.a, f.b):f.b; return {f.a/g, f.b/g};}
frac operator+(frac a, frac b){return red({a.a*b.b + b.a*a.b, a.b*b.b});}
frac operator-(frac a, frac b){return red({a.a*b.b - b.a*a.b, a.b*b.b});}
frac operator*(frac a, frac b){return red({a.a*b.a, a.b*b.b});}
frac operator/(frac a, frac b){return red({a.a*b.b, a.b*b.a});}
bool operator<(frac a, frac b){return a.a*b.b < b.a*a.b;}
bool operator<=(frac a, frac b){return a.a*b.b <= b.a*a.b;}
ll flr(frac a){return a.a/a.b;}
ll cil(frac a){return (a.a + a.b - 1)/a.b;}

const int N = 2022;
ll v[N][N]; ll ps[N][N];
bool done[N];
ll n, m;

frac nxt(frac f, int i){
	//f = red(f);
	//assert(f.b <= 1e9+10);
	//gd(cil(f)-f);
	frac sm = (cil(f)-f)*v[i][flr(f)];
	frac tsm = frac(ps[i][m])/n;
	//assert(flr(f)<m);
	if(tsm <= sm) return f + tsm/v[i][flr(f)];
	ll l = cil(f);
	//assert((tsm-sm).a > 0);
	ll r = lower_bound(ps[i], ps[i]+m+1, cil(tsm-sm+ps[i][l]))-ps[i];
	if(r==m+1) return m+10;
	--r;
	//assert(r>=0 && v[i][r]>0);
	sm = sm+ps[i][r]-ps[i][l];
	frac ans = r + (tsm - sm)/v[i][r];
	while(ans.b > 1e9) {ans.a = (ans.a+1)/2; ans.b = ans.b/2; ans = red(ans);}
	return ans;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	long long tmp;
	cin >> tmp; n=tmp;
	cin >> tmp; m=tmp;
	Loop(i,0,n) Loop(j,0,m){
		cin >> tmp;
		v[i][j]=tmp;
		ps[i][j+1] = ps[i][j]+v[i][j];
	}
	frac cur = 0;
	vector<pair<frac,int>> vec;
	Loop(i,0,n) {
		frac mn = m+1;
		int mni = -1;
		Loop(j,0,n){
			if(done[j]) continue;
			frac f = red(nxt(cur, j));
			if(f < mn){
				mn = f;
				mni = j;
			}
		}
		if(mni==-1) Kill(-1);
		done[mni]=1;
		vec.push_back({mn,mni});
		cur=mn;
	}
	Loop(i,0,n-1){
		cout << (long long)vec[i].first.a << ' ' << (long long)vec[i].first.b << '\n';
	}
	Loop(i,0,n) cout << vec[i].second+1 << ' ';
	cout << '\n';
}

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 460 KB Output is correct
18 Correct 1 ms 460 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 588 KB Output is correct
25 Correct 1 ms 588 KB Output is correct
26 Correct 1 ms 460 KB Output is correct
27 Correct 0 ms 332 KB Output is correct
28 Correct 1 ms 460 KB Output is correct
29 Correct 1 ms 588 KB Output is correct
30 Correct 1 ms 592 KB Output is correct
31 Correct 1 ms 588 KB Output is correct
32 Correct 1 ms 588 KB Output is correct
33 Correct 1 ms 588 KB Output is correct
34 Correct 1 ms 588 KB Output is correct
35 Correct 1 ms 588 KB Output is correct
36 Correct 1 ms 588 KB Output is correct
37 Correct 1 ms 588 KB Output is correct
38 Correct 0 ms 332 KB Output is correct
39 Correct 1 ms 588 KB Output is correct
40 Correct 1 ms 460 KB Output is correct
41 Correct 1 ms 332 KB Output is correct
42 Correct 1 ms 588 KB Output is correct
43 Incorrect 794 ms 13072 KB Expected int32, but "1394132287329" found
44 Halted 0 ms 0 KB -