Submission #702471

#	Time	Username	Problem	Language	Result	Execution time	Memory
702471		alvingogo	Naan (JOI19_naan)	C++14	100 / 100	705 ms	181624 KiB

naan

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

struct fac{
    int x,a,b;
    fac(){
        x=0;
        a=0;
        b=1;
    }
    fac(int c,int d,int e){
        x=c;
        if(d){
            int g=__gcd(d,e);
            a=d/g;
            b=e/g;
        }
        else{
            a=0;
            b=1;
        }
        if(a==b){
            x++;
            a=0;
        }
    }
    bool operator< (const fac& c) const{
        if(c.x!=x){
            return x<c.x;
        }
        return a*c.b<b*c.a;
    }
    void print(){
        cout << x*b+a << " " << b << "\n";
    }
};
signed main(){
    AquA;
    int n,l;
    cin >> n >> l;
    vector<vector<int> > v(n,vector<int>(l));
    vector<int> ave(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<l;j++){
            cin >> v[i][j];
            v[i][j]*=n;
            ave[i]+=v[i][j];
        }
        ave[i]/=n;
    }
    auto v2=v;
    vector<vector<fac> > dl(n);
    for(int i=0;i<n;i++){
        int nw=0;
        for(int j=0;j<l;j++){
            int y=ave[i]-nw;
            while(y<=v[i][j]){
                dl[i].push_back(fac(j,y,v[i][j]));
                y+=ave[i];
            }
            nw=(nw+v[i][j])%ave[i];
        }
        assert(dl[i].size()==n);
    }
    vector<int> vis(n);
    vector<int> z;
    for(int i=0;i<n;i++){
        int x=-1;
        for(int j=0;j<n;j++){
            if(!vis[j] && (x==-1 || dl[j][i]<dl[x][i])){
                x=j;
            }
        }
        if(i!=n-1){
            dl[x][i].print();
        }
        vis[x]=1;
        z.push_back(x);
    }
    
    for(auto h:z){
        cout << h+1 << " ";
    }
    cout << "\n";
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from naan.cpp:1:
naan.cpp: In function 'int main()':
naan.cpp:69:28: warning: comparison of integer expressions of different signedness: 'std::vector<fac>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   69 |         assert(dl[i].size()==n);
      |                ~~~~~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 24 / 24
• Subtask 3: 71 / 71