oj.uz

Submission #492817

# Submission time Handle Problem Language Result Execution time Memory
492817 2021-12-09T04:26:08 Z jiahng Naan (JOI19_naan) C++14
29 / 100
 388 ms 15876 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){
		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;
	}
};
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);
		FOR(j,1,L){
			frac k = frac(1, 1);
			while (!(cur + frac(A[i][j],1) * k < frac(sm, N))){
				B[i].pb(frac(j, 1) - k + (frac(sm,N) - cur) / A[i][j]);
				k = k - (frac(sm,N) - cur) / A[i][j];
				cur = frac(0,1);
			}
			cur = cur + frac(A[i][j], 1) * k;
		}
	}
	//~ 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 << ' ';
	
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from naan.cpp:2:
naan.cpp: In function 'int32_t main()':
naan.cpp:86:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<frac>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   assert(nxt != -1 && i < B[nxt].size());
      |                       ~~^~~~~~~~~~~~~~~

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 2 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 332 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 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 2 ms 332 KB Output is correct
16 Correct 2 ms 332 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 3 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 2 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 332 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 0 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 3 ms 332 KB Output is correct
30 Correct 2 ms 332 KB Output is correct
31 Correct 2 ms 332 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 3 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 388 ms 15876 KB Integer parameter [name=A_i] equals to -1922096429, violates the range [1, 2000000000000]
44 Halted 0 ms 0 KB -