oj.uz

Submission #524365

# Submission time Handle Problem Language Result Execution time Memory
524365 2022-02-09T06:21:23 Z ymm Naan (JOI19_naan) C++17
29 / 100
 35 ms 15900 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 long long 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;}
};
frac red(frac f){ll g = __gcd(f.a, 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;
int v[N][N]; ll ps[N][N];
bool done[N];
ll n, m;

frac nxt(frac f, int i){
	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);
	ll r = lower_bound(ps[i], ps[i]+m+1, tsm-sm+ps[i][l])-ps[i];
	if(r==m+1) return m+1;
	--r;
	assert(r>=0);
	sm = sm+ps[i][r]-ps[i][l];
	return r + (tsm - sm)/v[i][r];
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	Loop(i,0,n) Loop(j,0,m) cin >> v[i][j], 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 << vec[i].first.a << ' ' << 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 332 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 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 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 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 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 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 332 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 460 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 460 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 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 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 460 KB Output is correct
20 Correct 1 ms 460 KB Output is correct
21 Correct 1 ms 332 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 460 KB Output is correct
25 Correct 1 ms 460 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 0 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 460 KB Output is correct
30 Correct 1 ms 460 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 1 ms 460 KB Output is correct
33 Correct 1 ms 460 KB Output is correct
34 Correct 1 ms 460 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 460 KB Output is correct
37 Correct 1 ms 460 KB Output is correct
38 Correct 0 ms 332 KB Output is correct
39 Correct 1 ms 332 KB Output is correct
40 Correct 1 ms 332 KB Output is correct
41 Correct 1 ms 332 KB Output is correct
42 Correct 1 ms 332 KB Output is correct
43 Runtime error 35 ms 15900 KB Execution killed with signal 6
44 Halted 0 ms 0 KB -