Submission #1170090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170090		Piokemon	Naan (JOI19_naan)	C++20	29 / 100	82 ms	6728 KiB

naan

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

pair<ll,ll> fix(pair<ll,ll> a){
    ll d = __gcd(a.first,a.second);
    return {a.first/d,a.second/d};
}

pair<ll,ll> operator+(pair<ll,ll> a, pair<ll,ll> b){
    return fix({a.first*b.second+b.first*a.second,a.second*b.second});
}
pair<ll,ll> operator-(pair<ll,ll> a, pair<ll,ll> b){
    return fix({a.first*b.second-b.first*a.second,a.second*b.second});
}
pair<ll,ll> operator*(pair<ll,ll> a, pair<ll,ll> b){
    return fix({a.first*b.first,a.second*b.second});
}

bool operator>=(pair<ll,ll> a, pair<ll,ll> b){
    return (a.first*b.second >= a.second*b.first);
}

constexpr int N = 2000;
constexpr int L = 2000;
pair<ll,ll> v[N+9][L+9];
pair<ll,ll> cel[N+9];
pair<ll,ll> ter[N+9];
vector<int> p;
bool used[N+9];

void check(int n, int l){
    pair<ll,ll> poprz={0,1};
    int poz=1;
    pair<ll,ll> ter={0,1};
    for (int x=0;x<n;x++){
        while(cel[p[x]] >= ter + v[p[x]][poz] * make_pair(poprz.second-poprz.first,poprz.second)){
            ter =ter+ v[p[x]][poz++] * make_pair(poprz.second-poprz.first,poprz.second);
            poprz={0,1};
        }
        // brakuje cel-ter
    } 
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,l;
    cin >> n >> l;
    for (int x=1;x<=n;x++){
        for (int y=1;y<=l;y++){
            cin >> v[x][y].first; v[x][y].second=1;
            cel[x].first+=v[x][y].first;
        }
        ter[x] = {0,1};
        cel[x].second=n;
    }
    pair<ll,ll> poprz={0,1};
    int poz=1;
    while(p.size()!=n-1){
        vector<int> done;
        for (int x=1;x<=n;x++){
            if (used[x])continue;
            pair<ll,ll> temp = make_pair(poprz.second-poprz.first,poprz.second) * v[x][poz];
            if (temp+ter[x] >= cel[x])done.push_back(x);
        }
        if (done.empty()){
            for (int x=1;x<=n;x++){
                if (used[x])continue;
                pair<ll,ll> temp = make_pair(poprz.second-poprz.first,poprz.second) * v[x][poz];
                ter[x] = ter[x]+temp;
            }
            poz++;
            poprz={0,1};
            continue;
        }
        int best=0; pair<ll,ll> kiedy = {1e9,1};
        for (int x:done){
            pair<ll,ll> temp = cel[x]-ter[x]; temp.second *= v[x][poz].first;
            if (kiedy>=temp){kiedy=temp;best=x;}
        }
        p.push_back(best);used[best]=1;
        kiedy = kiedy+poprz;
        poprz=kiedy;
        for (int x=0;x<=n;x++)ter[x]={0,1};
        kiedy = kiedy + make_pair(poz-1,1);
        cout << kiedy.first << ' ' << kiedy.second << '\n';
    }
    for (int x=1;x<=n;x++){
        if (!used[x])p.push_back(x);
    }
    for (int x:p) cout << x << ' ';
    cout << '\n';
}

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