Submission #201371

#	Time	Username	Problem	Language	Result	Execution time	Memory
201371		BThero	Naan (JOI19_naan)	C++17	29 / 100	972 ms	56952 KiB

naan

// Why am I so dumb? :c
// chrono::system_clock::now().time_since_epoch().count()
                                                  
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;   
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)2e3 + 5;

struct Ratio {
    ll a, b;

    Ratio() {
        a = 0;
        b = 1;
    }

    Ratio(ll a, ll b) : a(a), b(b) {}

    void simplify() {
        ll c = __gcd(a, b);
        a /= c;
        b /= c;
    }         
};         

bool operator < (Ratio f, Ratio s) {
    return f.a * s.b < f.b * s.a;
}

bool operator > (Ratio f, Ratio s) {
    return s < f;
}

bool operator == (Ratio f, Ratio s) {
    return !(f < s) && !(f > s);
}

bool operator <= (Ratio f, Ratio s) {
    return f < s || f == s;
}

bool operator >= (Ratio f, Ratio s) {
    return s <= f;
}

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

Ratio operator + (Ratio f, Ratio s) {
    ll c = lcm(f.b, s.b);
    return Ratio(f.a * c / f.b + s.a * c / s.b, c);
}

void operator += (Ratio &f, Ratio s) {
    f = f + s;
}

vector<Ratio> V[MAXN];

ll arr[MAXN][MAXN];

bool used[MAXN];

int ptr[MAXN];

int n, m;

void solve() {
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; ++i) {
        ll mean = 0, cur = 0;

        for (int j = 1; j <= m; ++j) {
            scanf("%lld", &arr[i][j]);
            mean += arr[i][j];
            arr[i][j] *= n;
        }

        Ratio r(0, 1);

        for (int j = 1; j <= m; ++j) {
            ll X = arr[i][j];

            while (X > 0) {
                if (cur + X > mean) {
                    r += Ratio(mean - cur, arr[i][j]);
                    r.simplify();
                    X -= (mean - cur);
                    cur = mean;                    
                }
                else {
                    cur += X;
                    r += Ratio(X, arr[i][j]);
                    r.simplify();
                    X = 0;
                }

                if (cur == mean) {
                    V[i].pb(r);
                    cur = 0;
                }
            }                    
        }

        assert(V[i].size() == n);                        
    }

    vector<int> perm;
    
    for (int j = 0; j < n; ++j) {
        int best = -1;                
        
        for (int i = 1; i <= n; ++i) {
            if (!used[i]) {
                if (best == -1 || V[i][j] < V[best][j]) {
                    best = i;
                }                        
            }
        }

        assert(best != -1);
        used[best] = 1;

        if (j + 1 < n) {
            printf("%lld %lld\n", V[best][j].a, V[best][j].b);
        }

        perm.pb(best);
    }

    for (int x : perm) {
        printf("%d ", x);
    }
}

int main() {
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from naan.cpp:4:
naan.cpp: In function 'void solve()':
naan.cpp:123:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(V[i].size() == n);                        
                ~~~~~~~~~~~~^~~~
naan.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
naan.cpp:92:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%lld", &arr[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~

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