제출 #1129280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129280		antonn	Naan (JOI19_naan)	C++20	컴파일 에러	0 ms	0 KiB

naan

#include <bits/stdc++.h>


using namespace std;


#define ll long long
#define ld long double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()


int n, L;
vector<vector<int>> v;
vector<vector<ll>> pref;


mt19937 rng((long long) (new char));


struct Frac {
    ll p;
    ll q;

    Frac(ll a = 0, ll b = 1) : p(a), q(b) {}

    ll getIntValue() {
        return p / q;
    }
};


bool operator <= (Frac a, Frac b) {
    return 1LL * a.p * b.q <= 1LL * a.q * b.p;
}


ll lcm(ll a, ll b) {
    return a * b / __gcd(a, b);
}


Frac operator + (Frac a, Frac b) {
    Frac c = {0, 0};
    ll d = lcm(a.q, b.q);
    c.p = a.p * (d / a.q) + b.p * (d / b.q);
    c.q = d;
    return c;
}


Frac operator - (Frac a, Frac b) { 
    assert(b <= a);
    Frac c;
    ll d = lcm(a.q, b.q);
    c.p = a.p * (d / a.q) - b.p * (d / b.q);
    c.q = d;
    return c;
}


Frac operator * (int x, Frac f) {
    return {f.p * x, f.q};
}


Frac operator / (Frac f, int x) {
    return {f.p, f.q * x};
}


int32_t main() {
    if (1) {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
	}
	cin >> n >> L;
    v.assign(n + 1, vector<int>(L + 2));
    pref.assign(n + 1, vector<ll>(L + 1));
    vector<Frac> need(n + 1);
    for (int i = 1; i <= n; i += 1) {
        ll sum = 0;
        for (int j = 1; j <= L; j += 1) {
            cin >> v[i][j];
            sum += v[i][j];
            pref[i][j] = pref[i][j - 1] + v[i][j];
        }
        v[i][L + 1] = 1;
        need[i] = {sum, n};
        need[i].reduce();
    }
    vector<pair<int, Frac>> sol;
    for (int step = 1; step <= 100; step += 1) {
        vector<int> ord(n);
        iota(all(ord), 1);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);
        shuffle(all(ord), rng);

        vector<pair<int, Frac>> cur;
        Frac eaten = {0, 1};
        int full = 0;
        bool bad = 0;
        for (auto i : ord) {
            Frac split;
            if (full == L) {
                bad = 1;
                break;
            }
            if (need[i] <= v[i][full + 1] * (Frac(full + 1, 1) - eaten)) {
                split = eaten + (need[i] / v[i][full + 1]);
                split.reduce();
            } else {
                Frac aux = need[i];
                aux = aux - v[i][full + 1] * (Frac(full + 1, 1) - eaten);
                split.reduce();
                assert(Frac(0, 1) <= aux);
                int low = full + 2, high = L, sol = full + 1;
                while (low <= high) {
                    int m = (low + high) / 2;
                    if (Frac(pref[i][m] - pref[i][full + 1], 1) <= aux) {
                        sol = m;
                        low = m + 1;
                    } else {
                        high = m - 1;
                    }
                }
                if (sol > L) {
                    bad = 1;
                    break;
                }
                aux = aux - Frac(pref[i][sol] - pref[i][full + 1], 1);
                split = sol + (aux / v[i][sol + 1]);
                split.reduce();
                if (!(split <= Frac(L, 1))) {
                    bad = 1;
                    break;
                }
            }
            eaten = split;
            full = eaten.getIntValue();
            cur.push_back({i, eaten});
        }
        if (bad == 0) {
            sol = cur;
            break;
        }
    }
    if (sol.size() != n) {
        cout << -1 << "\n";
        return 0;
    }
    
    for (int i = 0; i < sol.size() - 1; i += 1) {
        int who = sol[i].first;
        Frac split = sol[i].second;
        cout << split.p << " " << split.q << "\n";
    }
    for (int i = 0; i < sol.size(); i += 1) {
        int who = sol[i].first;
        Frac split = sol[i].second;
        cout << who << " ";
    }
    cout << "\n";
    return 0;
}

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

naan.cpp: In function 'int32_t main()':
naan.cpp:91:17: error: '__gnu_cxx::__alloc_traits<std::allocator<Frac>, Frac>::value_type' {aka 'struct Frac'} has no member named 'reduce'
   91 |         need[i].reduce();
      |                 ^~~~~~
naan.cpp:115:23: error: 'struct Frac' has no member named 'reduce'
  115 |                 split.reduce();
      |                       ^~~~~~
naan.cpp:119:23: error: 'struct Frac' has no member named 'reduce'
  119 |                 split.reduce();
      |                       ^~~~~~
naan.cpp:137:23: error: 'struct Frac' has no member named 'reduce'
  137 |                 split.reduce();
      |                       ^~~~~~