oj.uz

Submission #492818

# Submission time Handle Problem Language Result Execution time Memory
492818 2021-12-09T04:33:11 Z jiahng Naan (JOI19_naan) C++14
29 / 100
 230 ms 15916 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int __int128
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
//~ #define lbd(x, y) lower_bound(all(x), y)
//~ #define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef pair <pi,int> pii;
typedef long double ld;
#define maxn 2010
#define INF (ll)1e18
int MOD;
int32_t N, L, A[maxn][maxn];
bool done[maxn];
struct frac{
	int a, b;
	frac(int _a,int _b){
		assert(_b != 0);
		a = _a, b = _b;
		int x = __gcd(a,b); a /= x; b /= x;
	}
	frac operator+(frac y){
		return frac(y.a * b + y.b * a, y.b * b);
	}
	frac operator-(frac y){
		y.a *= -1;
		return *this + y;
	}
	frac operator/(int y){
		return frac(a, b * y);
	}
	frac operator*(int y){
		return frac(a*y,b);
	}
	frac operator*(frac y){
		return frac(a*y.a,b*y.b);
	}
	bool operator<(frac y){
		return (__int128) a * y.b < (__int128) b * y.a;
	}
	bool operator>=(frac y){
		return (__int128) a * y.b >= (__int128) b * y.a;
	}
};
vector <frac> B[maxn];

int32_t main(){
	fast;

	cin >> N >> L;
	FOR(i,1,N) FOR(j,1,L) cin >> A[i][j];
	
	FOR(i,1,N){
		int sm = accumulate(A[i]+1,A[i] + L + 1, 0LL);
		frac cur = frac(0, 1);
		int idx = 1;
		FOR(j,1,L){
			while (cur + frac(A[i][j],1) >= frac(idx*sm, N)){
				B[i].pb(frac(j-1, 1) + (frac(idx*sm,N) - cur) / A[i][j]);
				idx++;
			}
			cur = cur + frac(A[i][j], 1);
		}
	}
	//~ FOR(i,1,N){
		//~ cout << "Person " << i << '\n';
		//~ aFOR(j,B[i]){
			//~ cout << j.a << ' ' << j.b << '\n';
		//~ }
	//~ }
	//~ return 0;
	vector <frac> ans; vector <int32_t> P;
	FOR(i,0,N-2){
		int nxt = -1; 
		FOR(j,1,N) if (!done[j] && (nxt == -1 || B[j][i] < B[nxt][i])) nxt = j;
		done[nxt] = 1;
		//~ assert(nxt != -1 && i < B[nxt].size());
		ans.pb(B[nxt][i]);
		P.pb(nxt);
	}
	FOR(i,1,N) if (!done[i]) P.pb(i);
	aFOR(i,ans){
		cout << int32_t(i.a) << ' ' << int32_t(i.b) << '\n';
	}
	aFOR(i,P) cout << i << ' ';
	
}

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 1 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 392 KB Output is correct
9 Correct 0 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 1 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 2 ms 332 KB Output is correct
5 Correct 2 ms 332 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 2 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 412 KB Output is correct
16 Correct 4 ms 420 KB Output is correct
17 Correct 2 ms 332 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 2 ms 332 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 2 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 2 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 2 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 1 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 392 KB Output is correct
9 Correct 0 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 1 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 2 ms 332 KB Output is correct
20 Correct 2 ms 332 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 2 ms 332 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 2 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 2 ms 332 KB Output is correct
29 Correct 2 ms 332 KB Output is correct
30 Correct 2 ms 412 KB Output is correct
31 Correct 4 ms 420 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Correct 2 ms 332 KB Output is correct
34 Correct 2 ms 332 KB Output is correct
35 Correct 2 ms 332 KB Output is correct
36 Correct 2 ms 332 KB Output is correct
37 Correct 2 ms 332 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 2 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 2 ms 332 KB Output is correct
43 Incorrect 230 ms 15916 KB Integer parameter [name=A_i] equals to -1922096429, violates the range [1, 2000000000000]
44 Halted 0 ms 0 KB -