제출 #337401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337401		ryangohca	Naan (JOI19_naan)	C++17	29 / 100	257 ms	130028 KiB

naan

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
struct fraction {
    __int128_t n, d;
    fraction(__int128_t _n, __int128_t _d) {
        n = _n, d = _d;
        __int128_t g = std::__gcd(n, d); n /= g, d /= g;
        if (d < 0) n *= -1, d *= -1;
    }
    fraction(__int128_t _n) : fraction(_n, 1) {}
    fraction() : fraction(0) {}
    friend bool operator < (const fraction& l, const fraction& r) { return l.n * r.d < r.n * l.d; }
    friend bool operator <= (const fraction& l, const fraction& r) { return l.n * r.d <= r.n * l.d; }
    friend bool operator > (const fraction& l, const fraction& r) { return l.n * r.d > r.n * l.d; }
    friend bool operator >= (const fraction& l, const fraction& r) { return l.n * r.d >= r.n * l.d; }
    friend bool operator == (const fraction& l, const fraction& r) { return l.n == r.n && l.d == r.d; }
    friend bool operator != (const fraction& l, const fraction& r) { return !(l == r); }
    fraction operator - () const { return fraction(-n, d); }
    friend fraction operator + (const fraction& l, const fraction& r) { return fraction(l.n * r.d + r.n * l.d, l.d * r.d); }
    friend fraction operator - (const fraction& l, const fraction& r) { return fraction(l.n * r.d - r.n * l.d, l.d * r.d); }
    friend fraction operator * (const fraction& l, const fraction& r) { return fraction(l.n * r.n, l.d * r.d); }
    friend fraction operator * (const fraction& l, int r) { return l * fraction(r, 1); }
    friend fraction operator * (int r, const fraction& l) { return l * r; }
    friend fraction operator / (const fraction& l, const fraction& r) { return l * fraction(r.d, r.n); }
    friend fraction operator / (const fraction& l, const int& r) { return l / fraction(r, 1); }
    friend fraction operator / (const int& l, const fraction& r) { return fraction(l, 1) / r; }
    friend fraction& operator += (fraction& l, const fraction& r) { return l = l + r; }
    friend fraction& operator -= (fraction& l, const fraction& r) { return l = l - r; }
    template <class T> friend fraction& operator *= (fraction& l, const T& r) { return l = l * r; }
    template <class T> friend fraction& operator /= (fraction& l, const T& r) { return l = l / r; }
};
 
int nums[2000][2000];
fraction cuts[2000][2000];
vector<fraction> confirmed;
vector<int> order;
bool ordered[2000];
inline int read() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch & 15);
		ch = getchar_unlocked();
	}
	return x;
}
main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n = read(), l = read();
    fraction zero = fraction(0, 1), one = fraction(1, 1);
    for (int i = 0; i < n; i++){
        fraction need;
        for (int j = 0; j < l; j++) {
            nums[i][j] = read();
            need += fraction(nums[i][j], 1);
        }
        need /= fraction(n, 1);
        fraction curr, prevleft;
        int idx = 0;
        for (int j = 1; j < n; j++){
            while (need > curr){
                fraction willtake = (one - prevleft) * fraction(nums[i][idx], 1);
                if (curr + willtake <= need){
                    curr += willtake;
                    idx++;
                    prevleft = zero;
                } else {
                    prevleft = (need - curr) / fraction(nums[i][idx], 1);
                    curr = need;
                    break;
                }
            }
            cuts[i][j] = fraction(idx, 1) + prevleft;
            curr = fraction(0, 1);
        }
    }
    for (int i = 1; i < n; i++){ // cut i
        pair<fraction, int> giveCut = {fraction(1e9, 1), -1};
        for (int j = 0; j < n; j++){ // person j
            if (!ordered[j]) {
                pair<fraction, int> other = {cuts[j][i], j};
                giveCut = min(giveCut, other);
            }
        }
        ordered[giveCut.second] = true;
        confirmed.push_back(giveCut.first);
        order.push_back(giveCut.second);
    }
    for (int i = 0; i < n; i++){
        if (!ordered[i]) order.push_back(i);
    }
    for (fraction i : confirmed){
        cout << (int)i.n << ' ' << (int)i.d << '\n';
    }
    for (auto i : order) cout << i + 1 << ' ';
    cout << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

naan.cpp:50:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      |      ^

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