oj.uz

Submission #524419

# Submission time Handle Problem Language Result Execution time Memory
524419 2022-02-09T07:51:40 Z ymm Naan (JOI19_naan) C++17
0 / 100
 2 ms 460 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;


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

ll get(ll l, ll r, int i){
	return (ps[i][r/den]-ps[i][l/den])*den + (r%den)*v[i][r/den] - (l%den)*v[i][l/den];
}

ll nxt(ll f, int i){
	ll l=f, r=den*m+1;
	while(l<r){
		ll mid = (l+r)/2;
		if(get(f,mid,i)>=ps[i][m]*den/n) r=mid;
		else                             l=mid+1;
	}
	return l;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> m;
	den = n*m;
	Loop(i,0,n) Loop(j,0,m){
		cin >> v[i][j];
		ps[i][j+1] = ps[i][j]+v[i][j];
	}
	ll cur = 0;
	vector<pair<ll,int>> vec;
//	cout << get(0,28,1) << "?\n";
	Loop(i,0,n) {
		ll mn = den*m+1;
		int mni = -1;
		Loop(j,0,n){
			if(done[j]) continue;
			ll f = 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;
//		cout << mn<<' '<<mni << "!\n";
	}
	Loop(i,0,n-1){
		cout << vec[i].first << ' ' << den << '\n';
	}
	Loop(i,0,n) cout << vec[i].second+1 << ' ';
	cout << '\n';
}

Subtask #1
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 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 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 Incorrect 1 ms 332 KB Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000]
12 Halted 0 ms 0 KB -

Subtask #2
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 460 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 0 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 460 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 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 460 KB Output is correct
21 Correct 1 ms 460 KB Output is correct
22 Correct 1 ms 460 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Incorrect 2 ms 460 KB Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000]
25 Halted 0 ms 0 KB -

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 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 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 Incorrect 1 ms 332 KB Integer parameter [name=A_i] equals to -1, violates the range [1, 2000000000000]
12 Halted 0 ms 0 KB -