Submission #702418

#	Time	Username	Problem	Language	Result	Execution time	Memory
702418		PixelCat	Naan (JOI19_naan)	C++14	29 / 100	3 ms	724 KiB

naan

#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 F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;

struct Frac {
    int x, y;
    Frac(int _x = 0, int _y = 1) {
        x = _x; y = _y;
        simp();
    }
    void simp() {
        int g = __gcd(x, y);
        x /= g; y /= g;
    }
};
Frac operator-(const Frac &a) {
    return Frac(-a.x, a.y);
}
Frac operator+(const Frac &a, const Frac &b) {
    return Frac(a.x * b.y + a.y * b.x, a.y * b.y);
}
Frac operator-(const Frac &a, const Frac &b) {
    return a + (-b);
}
Frac operator*(const Frac &a, const Frac &b) {
    return Frac(a.x * b.x, a.y * b.y);
}
Frac operator/(const Frac &a, const Frac &b) {
    return Frac(a.x * b.y, a.y * b.x);
}
bool operator==(const Frac &a, const Frac &b) {
    return a.x * b.y == a.y * b.x;
}
bool operator<(const Frac &a, const Frac &b) {
    return a.x * b.y < a.y * b.x;
}
bool operator>(const Frac &a, const Frac &b) {
    return b < a;
}
bool operator<=(const Frac &a, const Frac &b) {
    return a < b || a == b;
}
bool operator>=(const Frac &a, const Frac &b) {
    return a > b || a == b;
}

const int MAXN = 2010;

int v[MAXN][MAXN];
Frac tar[MAXN];
int ids[MAXN];
Frac rem[MAXN];
Frac x[MAXN];

bool check(int n, int l) {
    For(i, 1, l) rem[i] = Frac(1);
    int pos = 1;
    For(it, 1, n) {
        int id = ids[it];
        Frac now(0);
        while(now + rem[pos] * v[id][pos] < tar[id]) {
            if(pos == l) return false;
            now = now + rem[pos] * v[id][pos];
            pos++;
        }
        Frac owo = (tar[id] - now) / v[id][pos];
        assert(owo <= 1);
        rem[pos] = rem[pos] - owo;
        x[it] = pos - rem[pos];
    }
    return true;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // nyanyanyanyanya
    int n, l; cin >> n >> l;
    assert(n <= 6);
    For(i, 1, n) {
        tar[i] = Frac();
        For(j, 1, l) {
            cin >> v[i][j];
            tar[i].x += v[i][j];
        }
        tar[i] = tar[i] / n;
    }
    For(i, 1, n) ids[i] = i;
    do {
        if(check(n, l)) {
            For(i, 1, n - 1) cout << x[i].x << " " << x[i].y << "\n";
            For(i, 1, n) cout << ids[i] << " \n"[i == n];
            return 0;
        }
    } while(next_permutation(ids + 1, ids + n + 1));
    assert(false);
    return 0;
}

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