oj.uz

Submission #379050

# Submission time Handle Problem Language Result Execution time Memory
379050 2021-03-17T08:48:49 Z urd05 Naan (JOI19_naan) C++14
29 / 100
 58 ms 11116 KB 
#include <bits/stdc++.h>
using namespace std;

int arr[2000][2000];
typedef pair<long long,long long> P; //first/second
typedef pair<P,int> Pi;
bool used[2000];

bool comp(Pi a,Pi b) {
    return (__int128)a.first.first*b.first.second<(__int128)b.first.first*a.first.second;
}

P save[2000][2000];

int main(void) {
    int n,l;
    scanf("%d %d",&n,&l);
    for(int i=0;i<n;i++) {
        for(int j=0;j<l;j++) {
            scanf("%d",&arr[i][j]);
        }
    }
    for(int i=0;i<n;i++) {
        int ind=1;
        long long sum=0;
        for(int j=0;j<l;j++) {
            sum+=arr[i][j];
        }
        long long temp=0;
        for(int j=0;j<l;j++) {
            while (ind<n&&(temp+arr[i][j])*n>=sum*ind) {
                save[i][ind]=P(sum*ind-n*temp+j*n*arr[i][j],n*arr[i][j]);
                ind++;
            }
            temp+=arr[i][j];
        }
    }
    vector<P> ret;
    vector<int> v;
    for(int cnt=n-1;cnt>0;cnt--) {
        vector<Pi> vec;
        for(int i=0;i<n;i++) {
            if (!used[i]) {
                vec.push_back(Pi(save[i][cnt],i));
            }
        }
        sort(vec.begin(),vec.end(),comp);
        reverse(vec.begin(),vec.end());
        used[vec[0].second]=true;
        v.push_back(vec[0].second);
        ret.push_back(vec[0].first);
    }
    reverse(ret.begin(),ret.end());
    for(int i=0;i<n;i++) {
        if (!used[i]) {
            v.push_back(i);
        }
    }
    reverse(v.begin(),v.end());
    for(int i=0;i<ret.size();i++) {
        printf("%lld %lld\n",ret[i].first,ret[i].second);
    }
    for(int i=0;i<v.size();i++) {
        printf("%d ",v[i]+1);
    }
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(int i=0;i<ret.size();i++) {
      |                 ~^~~~~~~~~~~
naan.cpp:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
naan.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |     scanf("%d %d",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~
naan.cpp:20:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   20 |             scanf("%d",&arr[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

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

Subtask #3
0 / 71.0

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