Submission #201387

#	Time	Username	Problem	Language	Result	Execution time	Memory
201387		BThero	Naan (JOI19_naan)	C++17	100 / 100	787 ms	96248 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) {}             
};         
 
bool operator < (Ratio f, Ratio s) {
    return (double)f.a / f.b < (double)s.a / s.b;
}
 
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;
        }
 
        ll pref = 0;
 
        for (int j = 1; j <= m; ++j) {
            ll Y = 0, X = arr[i][j];
 
            while (Y < X) {
                if (cur + (X - Y) > mean) {
                    Y += (mean - cur);
                    cur = mean;                                                                                                                                                                                           
                }
                else {
                    cur += (X - Y);
                    Y = X;        
                }
 
                if (cur == mean) {
                    V[i].pb(Ratio((j - 1) * X + Y, X));
                    cur = 0;
                }
            }
 
            pref += X;      
        }
 
        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:86:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         assert(V[i].size() == n);                        
                ~~~~~~~~~~~~^~~~
naan.cpp:51: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:57: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: 71 / 71