Submission #484452

#	Time	Username	Problem	Language	Result	Execution time	Memory
484452		Marslai24	Naan (JOI19_naan)	C++17	0 / 100	1 ms	332 KiB

naan

#include <bits/stdc++.h>
using namespace std;
#define int long long // a.k.a. TLE creator
#define all(x) x.begin(), x.end()

template<class A, class B> istream &operator >>(istream &o, pair<A, B> &x){return o >> x.first >> x.second, o;}
template<class A, class B> ostream &operator <<(ostream &o, pair<A, B> &x){return o << x.first << ' ' << x.second, o;}

const int INF = 4e18, MOD = 1e9 + 7, N = 1e5 + 10, K = __lg(N) + 1;

void setIO(){ios::sync_with_stdio(false); cin.tie(0);}

struct frac{
    int p, q;
    frac(){p = 0, q = 1;}
    frac(int _p, int _q) : p(_p), q(_q){}
    int gcd(int a, int b){return b ? gcd(b, a % b) : a;}
    void simple(){
        int g = gcd(p, q);
        if(!g)return;
        p /= g, q /= g;
    }
    bool operator <(const frac &o)const{
        return p * o.q < o.p * q;
    }
    bool operator ==(const frac &o)const{
        return p == o.p && q == o.q;
    }
    frac operator +(const frac &o)const{
        frac ans;
        ans.q = q * o.q;
        ans.p = p * o.q + o.p * q;
        ans.simple();
        return ans;
    }
    frac operator -(const frac &o)const{
        frac ans;
        ans.q = q * o.q;
        ans.p = p * o.q - o.p * q;
        ans.simple();
        return ans;
    }
    frac operator *(const frac &o)const{
        frac ans(p * o.p, q * o.q);
        ans.simple();
        return ans;
    }
    frac operator /(const frac &o)const{
        frac ans(p * o.q, o.p * q);
        ans.simple();
        return ans;
    }
    void print(){
        cout << p << ' ' << q << endl;
    }
};

signed main(){
    setIO();
    int n, l;
    cin >> n >> l;
    frac a[n][l];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < l; j++){
            int x;
            cin >> x;
            a[i][j] = frac(x, 1);
        }
    }
    vector<pair<frac, int>> best[n];
    for(int i = 0; i < n; i++){
        int cnt = 0;
        frac tar, now, pre, ptr;
        for(int j = 0; j < l; j++)tar = tar + a[i][j];
        tar = tar / frac(n, 1);
        tar.simple();
        for(int j = 0; j < l; ){
            now.simple(); pre.simple();
            if(now + a[i][j] * (frac(1, 1) - ptr) - pre < tar){
                now = now + a[i][j] * (frac(1, 1) - ptr);
                ptr = frac();
                j++;
            }else{
                frac rem = tar - (now - pre);
                rem = rem / a[i][j];
                now = now + rem;
                best[cnt++].push_back({now, i});
                pre = now;
                ptr = ptr + rem;
                ptr.simple();
                if(ptr == frac(1, 1))j++;
            }
        }
    }
    for(int i = 0; i < n; i++){
        sort(all(best[i]));
    }
    bool vis[n]{};
    vector<int> ans;
    for(int i = 0; i < n; i++){
        for(auto [j, k] : best[i]){
            if(!vis[k]){
                if(i != n - 1)j.print();
                vis[k] = 1;
                ans.push_back(k + 1);
                break;
            }
        }
    }
    for(int i : ans)cout << i << ' ';
}

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