oj.uz

Submission #703793

# Submission time Handle Problem Language Result Execution time Memory
703793 2023-02-28T12:11:00 Z Darren0724 Naan (JOI19_naan) C++17
29 / 100
 171 ms 66444 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int INF=1e18;
bool operator<(pair<int,int> a,pair<int,int> b){
    return a.first*b.second<a.second*b.first;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    vector<int> a(n);
    vector<vector<int>> v(n,vector<int>(m)),pre(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>v[i][j];
            v[i][j]*=n;
            a[i]+=v[i][j];
        }
        a[i]/=n;
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout<<v[i][j]<<' ';
        }
        cout<<endl;
    }*/
    for(int i=0;i<n;i++){
        pre[i][0]=v[i][0];
        for(int j=1;j<m;j++){
            pre[i][j]=pre[i][j-1]+v[i][j];
        }
    }
    vector<bool> vis(n);
    vector<vector<pair<int,int>>> rec(n,vector<pair<int,int>>(n));
    for(int i=0;i<n;i++){
        int need=0;
        int ptr=0;
        for(int j=0;j<n-1;j++){
            need+=a[i];
            while(ptr<m-1&&pre[i][ptr]<need){
                ptr++;
            }
            int p=(ptr>0?pre[i][ptr-1]:0);
            rec[i][j]={need-p+ptr*v[i][ptr],v[i][ptr]};
        }
    }
    /*for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<"("<<rec[i][j].first<<","<<rec[i][j].second<<") ";
        }
        cout<<endl;
    }*/
    vector<int> ans(n);
    for(int i=0;i<n-1;i++){
        int idx=-1;
        for(int j=0;j<n;j++){
            if(vis[j]){
                continue;
            }
            if(idx==-1){
                idx=j;
            }
            else if(rec[j][i]<rec[idx][i]){
                idx=j;
            }
        }
        ans[i]=idx+1;
        vis[idx]=1;
        cout<<rec[idx][i].first<<' '<<rec[idx][i].second<<endl;
    }
    for(int i=0;i<n;i++){
        if(vis[i]==0){
            ans[n-1]=i+1;
        }
    }
    for(int j=0;j<n;j++){
        cout<<ans[j]<<' ';
    }




    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 448 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 404 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 2 ms 460 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 320 KB Output is correct
27 Correct 1 ms 456 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 316 KB Output is correct
7 Correct 1 ms 320 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 448 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 324 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 2 ms 404 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 2 ms 460 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 320 KB Output is correct
42 Correct 1 ms 456 KB Output is correct
43 Correct 38 ms 9536 KB Output is correct
44 Incorrect 171 ms 66444 KB X_i is not increasing
45 Halted 0 ms 0 KB -