Submission #1170025

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170025		jerzyk	Naan (JOI19_naan)	C++20	100 / 100	508 ms	63320 KiB

naan

#include <bits/stdc++.h>

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 2007;
ll tab[N];
pair<ll, ll> pos[N][N];
pair<ll, ll> ans[N];
int wh[N];
bool tk[N];

bool Cp(pair<ll, ll> a, pair<ll, ll> b)
{
    __int128 x = a.st, y = a.nd, u = b.st, v = b.nd;
    return (x * v < y * u);
}

ll GCD(ll a, ll b)
{
    ll c;
    while(b > 0LL)
    {
        c = b;
        b = a % b;
        a = c;
    }
    return a;
}

void Solve()
{
    int n, k; string s;
    cin >> n >> k;
    for(int l = 1; l <= n; ++l)
    {
        ll s = 0LL;
        for(int i = 1; i <= k; ++i)
        {
            cin >> tab[i]; s += tab[i];
            tab[i] *= (ll)n;
        }
        ll cur = 0LL;
        int j = 1;
        for(int i = 1; i < n; ++i)
        {
            cur += s;
            while(tab[j] <= cur)
                {cur -= tab[j]; ++j;}
            pos[l][i] = make_pair(cur, tab[j]);
            ll g = GCD(cur, tab[j]);
            pos[l][i].st /= g; pos[l][i].nd /= g;
            pos[l][i].st += (ll)(j - 1) * pos[l][i].nd;
        }
    }
    for(int l = 1; l < n; ++l)
    {
        pair<ll, ll> cur = make_pair((ll)(k + 2), 1LL); int v = -1;
        for(int i = 1; i <= n; ++i)
        {
            if(tk[i]) continue;
            if(Cp(pos[i][l], cur))
                {cur = pos[i][l]; v = i;}
        }
        ans[l] = cur;
        wh[l] = v; tk[v] = 1;
    }
    for(int i = 1; i <= n; ++i)
        if(!tk[i])
            wh[n] = i;
    for(int i = 1; i < n; ++i)
        cout << ans[i].st << " " << ans[i].nd << "\n";
    for(int i = 1; i <= n; ++i)
        cout << wh[i] << " ";
    cout << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //int t; cin >> t;
    //while(t--)
        Solve();

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 71 / 71