oj.uz

Submission #201371

# Submission time Handle Problem Language Result Execution time Memory
201371 2020-02-10T10:27:20 Z BThero Naan (JOI19_naan) C++17
29 / 100
 972 ms 56952 KB 
// 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 380 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 6 ms 376 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 7 ms 504 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 6 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 5 ms 380 KB Output is correct
13 Correct 6 ms 376 KB Output is correct
14 Correct 6 ms 504 KB Output is correct
15 Correct 6 ms 504 KB Output is correct
16 Correct 6 ms 504 KB Output is correct
17 Correct 6 ms 504 KB Output is correct
18 Correct 7 ms 504 KB Output is correct
19 Correct 6 ms 504 KB Output is correct
20 Correct 6 ms 376 KB Output is correct
21 Correct 7 ms 504 KB Output is correct
22 Correct 6 ms 504 KB Output is correct
23 Correct 5 ms 408 KB Output is correct
24 Correct 6 ms 504 KB Output is correct
25 Correct 6 ms 376 KB Output is correct
26 Correct 5 ms 376 KB Output is correct
27 Correct 6 ms 376 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 380 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 6 ms 376 KB Output is correct
13 Correct 6 ms 504 KB Output is correct
14 Correct 6 ms 376 KB Output is correct
15 Correct 6 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 6 ms 504 KB Output is correct
18 Correct 6 ms 376 KB Output is correct
19 Correct 7 ms 504 KB Output is correct
20 Correct 6 ms 504 KB Output is correct
21 Correct 6 ms 376 KB Output is correct
22 Correct 5 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 6 ms 504 KB Output is correct
25 Correct 6 ms 504 KB Output is correct
26 Correct 6 ms 376 KB Output is correct
27 Correct 5 ms 380 KB Output is correct
28 Correct 6 ms 376 KB Output is correct
29 Correct 6 ms 504 KB Output is correct
30 Correct 6 ms 504 KB Output is correct
31 Correct 6 ms 504 KB Output is correct
32 Correct 6 ms 504 KB Output is correct
33 Correct 7 ms 504 KB Output is correct
34 Correct 6 ms 504 KB Output is correct
35 Correct 6 ms 376 KB Output is correct
36 Correct 7 ms 504 KB Output is correct
37 Correct 6 ms 504 KB Output is correct
38 Correct 5 ms 408 KB Output is correct
39 Correct 6 ms 504 KB Output is correct
40 Correct 6 ms 376 KB Output is correct
41 Correct 5 ms 376 KB Output is correct
42 Correct 6 ms 376 KB Output is correct
43 Correct 120 ms 13552 KB Output is correct
44 Incorrect 972 ms 56952 KB X_i is not increasing
45 Halted 0 ms 0 KB -