이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
///
/// 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';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |