///
/// 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*2520;
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 && get(cur,f,j) == ps[j][m]*den/n){
mn = f;
mni = j;
}
}
if(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';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
324 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 |
320 KB |
Output is correct |
| 10 |
Correct |
1 ms |
316 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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
328 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 |
460 KB |
Output is correct |
| 12 |
Correct |
1 ms |
296 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 |
460 KB |
Output is correct |
| 21 |
Correct |
1 ms |
464 KB |
Output is correct |
| 22 |
Correct |
1 ms |
456 KB |
Output is correct |
| 23 |
Correct |
1 ms |
320 KB |
Output is correct |
| 24 |
Correct |
1 ms |
460 KB |
Output is correct |
| 25 |
Correct |
1 ms |
456 KB |
Output is correct |
| 26 |
Correct |
1 ms |
332 KB |
Output is correct |
| 27 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
1 ms |
316 KB |
Output is correct |
| 6 |
Correct |
1 ms |
324 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 |
320 KB |
Output is correct |
| 10 |
Correct |
1 ms |
316 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 |
- |
