| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 958162 | Tuanlinh123 | Naan (JOI19_naan) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define i128 __int128_t
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
const ll maxn=2005, big=1e9;
ll v[maxn][maxn];
i128 gcd(i128 x, i128 y)
{
while (y) tie(x, y)=mp(y, x%y);
return x;
}
struct frac
{
i128 x=0, y=1;
frac(){}
frac(i128 x): x(x), y(1) {}
frac(i128 x, i128 y): x(x), y(y){}
void fix() {if (y>big) {x=(x*big+y-1)/y, y=big;}}
frac operator + (const frac &o) const
{
frac ans={x*o.y+y*o.x, y*o.y};
i128 g=gcd(ans.x, ans.y);
ans.x/=g, ans.y/=g, ans.fix();
return ans;
}
frac operator - (const frac &o) const
{
frac ans={x*o.y-y*o.x, y*o.y};
ll g=__gcd(ans.x, ans.y);
ans.x/=g, ans.y/=g, ans.fix();
return ans;
}
frac operator / (const ll &v) const
{
i128 g=gcd(x, v);
frac ans={x/g, v/g*y}; ans.fix();
return ans;
}
frac operator * (const frac& o) const
{
frac ans={x*o.x, y*o.y};
i128 g=gcd(ans.x, ans.y);
ans.x/=g, ans.y/=g, ans.fix();
return ans;
}
bool operator >= (const frac &o) const
{
return x*o.y>=y*o.x;
}
bool operator <= (const frac &o) const
{
return x*o.y<=y*o.x;
}
};
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, m; cin >> n >> m;
for (ll i=1; i<=n; i++)
for (ll j=1; j<=m; j++)
cin >> v[i][j], v[i][j]+=v[i][j-1];
auto find=[&](ll id, frac h)
{
frac t=v[id][h.x/h.y];
t=t+frac(v[id][h.x/h.y+1]-v[id][h.x/h.y])*frac(h.x%h.y, h.y);
ll lo=1, hi=m;
t=t+frac(v[id][m], n);
while (hi>lo)
{
ll mid=(lo+hi)/2;
if (frac(v[id][mid])>=t)
hi=mid;
else lo=mid+1;
}
t=t-frac(v[id][lo-1]);
frac ans=frac(lo-1)+t/(v[id][lo]-v[id][lo-1]);
return ans;
};
vector <bool> used(n+1, 0);
frac crr;
vector <pll> res;
vector <ll> ans;
for (ll z=1; z<=n; z++)
{
pair<frac, ll> Max; Max.se=0;
for (ll i=1; i<=n; i++)
{
if (used[i]) continue;
frac to=find(i, crr);
if (to<=frac(m))
if (!Max.se || !(to>=Max.fi))
Max={to, i};
}
if (!Max.se) {cout << "-1"; exit(0);}
crr=Max.fi, used[Max.se]=1;
res.pb({crr.x, crr.y}), ans.pb(Max.se);
}
res.resize(n-1);
for (pll i:res) cout << i.fi << " " << i.se << "\n";
for (ll i:ans) cout << i << " ";
}