oj.uz

Submission #958201

# Submission time Handle Problem Language Result Execution time Memory
958201 2024-04-05T06:52:19 Z Tuanlinh123 Naan (JOI19_naan) C++17
29 / 100
 124 ms 11824 KB 
#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=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};
        i128 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]);
        if (ans.y==big) ans.x++;
        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 << " ";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 520 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 556 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 1 ms 352 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 484 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 480 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 520 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 1 ms 556 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 2 ms 348 KB Output is correct
37 Correct 1 ms 352 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 1 ms 484 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 1 ms 480 KB Output is correct
43 Incorrect 124 ms 11824 KB Not a fair distribution.
44 Halted 0 ms 0 KB -