Submission #535109

#	Time	Username	Problem	Language	Result	Execution time	Memory
535109		sare	Naan (JOI19_naan)	C++17	100 / 100	402 ms	88980 KiB

naan

//In the name of Allah :)
#include <bits/stdc++.h>
using namespace std;
string to_string(char c) { return string(1,c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return (string)s; }
string to_string(string s) { return s; }
template<class A> string to_string(complex<A> c) { 
    stringstream ss; ss << c; return ss.str(); }
string to_string(vector<bool> v) { 
    string res = "{"; for(int i = 0; i < (int)v.size(); i++) res += char('0'+v[i]);
    res += "}"; return res; }
template<size_t SZ> string to_string(bitset<SZ> b) {
    string res = ""; for(size_t i = 0; i < SZ; i++) res += char('0'+b[i]);
    return res; }
template<class A, class B> string to_string(pair<A,B> p);
template<class T> string to_string(T v) { // containers with begin(), end()
    bool fst = 1; string res = "{";
    for (const auto& x: v) {
        if (!fst) res += ", ";
        fst = 0; res += to_string(x);
    }
    res += "}"; return res;
}
template<class A, class B> string to_string(pair<A,B> p) {
    return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
    DBG(t...); }
#ifdef LOCAL // compile with -DLOCAL
#define wis(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "] : [", DBG(__VA_ARGS__)
#else
#define wis(...) 0
#endif
typedef long long ll;
typedef long double ld;
#define all(x) (x).begin(), (x).end()
const int MAXN = 2010;
int n, m, a[MAXN][MAXN];
bitset<MAXN> mark;
vector<int> out;

struct frac {
    ll x, y;

    frac () {
        x = 0, y = 1;
    }

    frac (ll _x, ll _y) {
        x = _x;
        y = _y;
    }

    inline bool operator < (const frac& he) {
        return (ld) x * he.y < (ld) he.x * y;
    }
};
vector<frac> where[MAXN];

int main() {
    ios::sync_with_stdio(0);
#ifndef LOCAL
    cin.tie(0);
#endif
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    for (int i = 0; i < n; ++i) {
        ll s = 0;
        for (int j = 0; j < m; ++j) {
            s += a[i][j];
        }
        int pos = 0;
        ll cur = 0;
        for (int j = 1; j < n; ++j) {
            while (n * (cur + a[i][pos]) < s * j) {
                cur += a[i][pos];
                pos++;
            }
            ll x = j * s - cur * n, y = n  * a[i][pos];
            frac p(x + pos * y, y);
            where[i].push_back(p);
        }
    }

    for (int i = 0; i < n - 1; ++i) {
        int p = -1;
        for (int j = 0; j < n; ++j) {
            if (mark[j]) {
                continue;
            }
            if (p == -1) {
                p = j;
                continue;
            }
            if (where[j][i] < where[p][i]) {
                p = j;
            }
        }
        mark[p] = 1;
        cout << where[p][i].x << ' ' << where[p][i].y << '\n';
        out.push_back(p + 1);
    }
    for (int i : out) {
        cout << i << ' ';
    }
    for (int i = 0; i < n; ++i) {
        if (!mark[i]) {
            cout << i + 1 << '\n';
        }
    }
}

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