Submission #710849

#	Time	Username	Problem	Language	Result	Execution time	Memory
710849		PixelCat	Naan (JOI19_naan)	C++14	100 / 100	767 ms	146888 KiB

naan

/* nya */
#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma")

#include <bits/stdc++.h>
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LLL
#define INF (int)(1e18)
#define MOD (int)(1000000007)
// #define MOD (int)(998244353)
using namespace std;
using LL = long long;
using LLL = __int128_t;
using pii = pair<int, int>;
 
#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}
#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#endif

bool smol(const pii &a, const pii &b) {
    return a.F * b.S < a.S * b.F;
}

pii owo(int a, int b) {
    int g = __gcd(a, b);
    return pii(a / g, b / g);
}

const int MAXN = 2010;

LL v0[MAXN];
LL v[MAXN];
pii dv[MAXN][MAXN];
int vis[MAXN];

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // OAO
    LL n, l; cin >> n >> l;
    For(i, 1, n) {
        int su = 0;
        For(j, 1, l) {
            cin >> v[j];
            su += v[j];
            v[j] *= n;
            v0[j] = v[j];
        }
        v[l + 1] = v0[l + 1] = 1;
        int ptr = 1;
        For(j, 1, n) {
            LL now = su;
            while(now > 0) {
                int x = min(now, v[ptr]);
                v[ptr] -= x;
                now -= x;
                if(v[ptr] == 0) ptr++;
            }
            dv[i][j] = owo(v0[ptr] - v[ptr] + v0[ptr] * (ptr - 1), v0[ptr]);
        }
    }
    vector<LL> res;
    For(rnd, 1, n) {
        pii mn(1e18, 1);
        int idx = -1;
        For(i, 1, n) if(!vis[i]) {
            if(smol(dv[i][rnd], mn)) {
                mn = dv[i][rnd];
                idx = i;
            }
        }
        mn = owo(mn.F, mn.S);
        if(rnd < n) cout << (LL)mn.F << " " << (LL)mn.S << "\n";
        res.eb(idx);
        vis[idx] = 1;
    }
    For(i, 0, n - 1) cout << res[i] << " \n"[i == n - 1];
    return 0;
}

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