Submission #237944

#	Time	Username	Problem	Language	Result	Execution time	Memory
237944		farmerboy	Naan (JOI19_naan)	C++14	100 / 100	546 ms	101240 KiB

naan

/*
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

const ll MODBASE = 1000000007LL;
const int MAXN = 2010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

int n, l, v[MAXN][MAXN];
ll num[MAXN][MAXN], den[MAXN][MAXN];
bool choose[MAXN];
vector<int> res;

bool isSmaller(int a, int b, int pos) {
    ld realPosB = (ld) num[b][pos] / den[b][pos];
    ld realPosA = (ld) num[a][pos] / den[a][pos];
    return realPosA < realPosB;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> l;
    FOR(i,1,n)
        FOR(j,1,l) cin >> v[i][j];
    FOR(i,1,n) {
        int s = 0;
        FOR(j,1,l) s += v[i][j];
        int curS = 0, itr = 0;
        FOR(j,1,n) {
            while ((ll) curS * n < (ll) s * j) curS += v[i][++itr];
            num[i][j] = (ll) itr * n * v[i][itr] - (ll) curS * n + (ll) s * j;
            den[i][j] = (ll) n * v[i][itr];
        }
    }
    FOR(i,1,n) {
        int vt = 0;
        FOR(j,1,n)
            if (!choose[j])
                if (!vt || isSmaller(j, vt, i)) vt = j;
        res.push_back(vt);
        choose[vt] = true;
    }
    FOR(i,0,n-2) cout << num[res[i]][i+1] << ' ' << den[res[i]][i+1] << "\n";
    FOR(i,0,n-1) cout << res[i] << ' ';
    return 0;
}

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