oj.uz

Submission #201915

# Submission time Handle Problem Language Result Execution time Memory
201915 2020-02-12T20:04:10 Z stefdasca Naan (JOI19_naan) C++14
29 / 100
 46 ms 14712 KB 
#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, l;
int mat[2002][2002];
ll num[2002][2002], den[2002][2002];

bool tk[2002];
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> l;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < l; ++j)
            cin >> mat[i][j];
    for(int i = 0; i < n; ++i)
    {
        int sum = 0;
        for(int j = 0; j < l; ++j)
            sum += mat[i][j];
        int cursum = 0;
        int pp = 0;
        for(int j = 0; j < n; ++j)
        {
            while(1LL * cursum * n < 1LL * sum * (j+1))
                cursum += mat[i][pp++];
            num[i][j] = 1LL * pp * n * mat[i][pp - 1] - cursum * n + sum * (j+1);
            den[i][j] = n * mat[i][pp - 1];
        }
    }
    vector<int> wh;
    for(int i = 0; i < n; ++i)
    {
        int cn = -1;
        for(int j = 0; j < n; ++j)
            if(!tk[j])
            {
                if(cn == -1 || ((0.0000 + num[cn][i]) / (0.0000 + den[cn][i]) > (0.0000 + num[j][i]) / (0.0000 + den[j][i])))
                    cn = j;
            }
        wh.pb(cn);
        tk[cn] = 1;
    }
    for(int i = 0; i + 1 < wh.size(); ++i)
        cout << num[wh[i]][i] << " " << den[wh[i]][i] << '\n';
    for(int i = 0; i < wh.size(); ++i)
        cout << wh[i] + 1 << " ";
    return 0;
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:65:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i + 1 < wh.size(); ++i)
                    ~~~~~~^~~~~~~~~~~
naan.cpp:67:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < wh.size(); ++i)
                    ~~^~~~~~~~~~~

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 5 ms 376 KB Output is correct
4 Correct 5 ms 372 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 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 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 376 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 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 5 ms 504 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 6 ms 504 KB Output is correct
15 Correct 5 ms 504 KB Output is correct
16 Correct 5 ms 504 KB Output is correct
17 Correct 6 ms 508 KB Output is correct
18 Correct 6 ms 504 KB Output is correct
19 Correct 6 ms 504 KB Output is correct
20 Correct 5 ms 504 KB Output is correct
21 Correct 6 ms 504 KB Output is correct
22 Correct 5 ms 504 KB Output is correct
23 Correct 5 ms 408 KB Output is correct
24 Correct 6 ms 376 KB Output is correct
25 Correct 5 ms 504 KB Output is correct
26 Correct 5 ms 380 KB Output is correct
27 Correct 5 ms 504 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 5 ms 376 KB Output is correct
4 Correct 5 ms 372 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 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 6 ms 376 KB Output is correct
18 Correct 5 ms 504 KB Output is correct
19 Correct 5 ms 504 KB Output is correct
20 Correct 5 ms 504 KB Output is correct
21 Correct 5 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 5 ms 504 KB Output is correct
25 Correct 5 ms 504 KB Output is correct
26 Correct 5 ms 504 KB Output is correct
27 Correct 5 ms 376 KB Output is correct
28 Correct 5 ms 376 KB Output is correct
29 Correct 6 ms 504 KB Output is correct
30 Correct 5 ms 504 KB Output is correct
31 Correct 5 ms 504 KB Output is correct
32 Correct 6 ms 508 KB Output is correct
33 Correct 6 ms 504 KB Output is correct
34 Correct 6 ms 504 KB Output is correct
35 Correct 5 ms 504 KB Output is correct
36 Correct 6 ms 504 KB Output is correct
37 Correct 5 ms 504 KB Output is correct
38 Correct 5 ms 408 KB Output is correct
39 Correct 6 ms 376 KB Output is correct
40 Correct 5 ms 504 KB Output is correct
41 Correct 5 ms 380 KB Output is correct
42 Correct 5 ms 504 KB Output is correct
43 Incorrect 46 ms 14712 KB X_i is not increasing
44 Halted 0 ms 0 KB -