Submission #699333

#	Time	Username	Problem	Language	Result	Execution time	Memory
699333		doowey	Naan (JOI19_naan)	C++14	29 / 100	380 ms	38124 KiB

naan

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 2010;
const ll C = (ll)1e18;

struct frac{
    ll A;
    ll B;
    frac operator+ (frac y){
        return {A * y.B + B * y.A, B * y.B};
    }
    frac operator- (frac y){
        return {A * y.B - B * y.A, B * y.B};
    }
    bool operator< (frac y){
        if(A/B == y.A/y.B){
            ll common = A/B;
            ll temp0 = A - B * common;
            ll temp1 = y.A - y.B * common;
            return (temp0 * y.B - B * temp1 < 0);
        }
        else{
            return A/B < y.A/y.B;
        }
    }
};

ll V[N][N];
ll S[N][N];
int m;

frac calc(int id, frac P){
    int las = P.A / P.B;
    frac Y = {S[id][las], 1};
    frac add = (P - (frac){las, 1});
    add.A *= V[id][las + 1];
    Y = Y + add;
    return Y;
}

frac need[N];
bool use[N];
int pi[N];

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n;
    cin >> n >> m;
    int vv;
    for(int i = 1; i <= n; i ++ ){
        need[i] = {0, n};
        for(int j = 1; j <= m ; j ++ ){
            cin >> vv;
            V[i][j] = vv;
            need[i].A += V[i][j];
            S[i][j] = V[i][j] + S[i][j - 1];
        }
        pi[i] = -1;
    }
    frac las = {0, 1};
    frac tis;
    frac nx;
    frac cur;
    frac low;
    int idx;
    frac SS;
    ll X;

    for(int it = 1; it < n; it ++ ){
        low = {m, 1};
        idx = -1;
        for(int i = 1; i <= n; i ++ ){
            if(!use[i]){
                tis = calc(i, las);
                for(int j = 1; j <= m; j ++ ){
                    nx = (frac){S[i][j], 1ll};
                    if(tis < nx){
                        SS = nx - tis;
                        SS = SS - need[i];
                        if(SS.A > 0){
                            SS.A *= (ll)n;
                            X = SS.A / SS.B;
                            tis = (frac){j, 1} - (frac){X, n * 1ll * V[i][j]};
                            if(tis < low){
                                low = tis;
                                idx = i;
                            }
                            break;
                        }
                    }
                }
            }
        }
        pi[it] = idx;
        use[idx]=true;
        las = low;
        cout << (long long)low.A << " " << (long long)low.B << "\n";
    }
    for(int i = 1; i <= n; i ++ ){
        if(!use[i]){
            pi[n]=i;
        }
    }
    for(int i = 1; i <= n; i ++ ){
        cout << pi[i] << " ";
    }
    cout << "\n";
    return 0;
}

Compilation message (stderr)

naan.cpp: In function 'int main()':
naan.cpp:74:10: warning: unused variable 'cur' [-Wunused-variable]
   74 |     frac cur;
      |          ^~~

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