제출 #337392

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

naan

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
struct fraction{
    int num, den;
    fraction(int num=0, int den=1):num(num), den(den){}
 
    void normalize(){
        int g = __gcd(num, den);
        num /= g;
        den /= g;
        if(den < 0){
            num = -num;
            den = -den;
        }
    }
 
    fraction operator-(){
        return fraction{-num, den};
    }
 
    fraction operator+=(const fraction &b){
        num = num*b.den + den*b.num;
        den = den*b.den;
        normalize();
        return *this;
    }
    fraction operator-=(const fraction &b){
        num = num*b.den - den*b.num;
        den = den*b.den;
        normalize();
        return *this;
    }
    fraction operator*=(const fraction &b){
        num = num*b.num;
        den = den*b.den;
        normalize();
        return *this;
    }
    fraction operator/=(const fraction &b){
        num = num*b.den;
        den = den*b.num;
        normalize();
        return *this;
    }
};
 
fraction operator+(fraction a, const fraction &b){return (a += b);}
fraction operator-(fraction a, const fraction &b){return (a -= b);}
fraction operator*(fraction a, const fraction &b){return (a *= b);}
fraction operator/(fraction a, const fraction &b){return (a /= b);}
bool operator==(const fraction &a, const fraction &b){return 1.0*a.num*b.den == 1.0*a.den*b.num;}
bool operator<(const fraction &a, const fraction &b){return 1.0*a.num*b.den < 1.0*a.den*b.num;}
bool operator>(const fraction &a, const fraction &b){return 1.0*a.num*b.den > 1.0*a.den*b.num;}
bool operator<=(const fraction &a, const fraction &b){return 1.0*a.num*b.den <= 1.0*a.den*b.num;}
bool operator>=(const fraction &a, const fraction &b){return 1.0*a.num*b.den >= 1.0*a.den*b.num;}

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 << i.num << ' ' << i.den << '\n';
    }
    for (auto i : order) cout << i + 1 << ' ';
    cout << '\n';
}

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

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

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