Submission #1290090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290090		jojeonghoon	Naan (JOI19_naan)	C++20	24 / 100	4094 ms	580 KiB

naan

#include <iostream>
#include <vector>
#include <set>
#include<algorithm>
#include<queue>
#include<map>
#include<math.h>
#include<assert.h>
#include<random>
#define ll long long
//#define int ll
#define db double
#define pii pair<int,int>
#define bk back()
using namespace std;

const int LM=2025;
int N,L;
int V[LM][LM], Vsum[LM];

int Gcd(int x, int y){
    if(x<y) swap(x,y);
    if(y==0) return x;
    return Gcd(y, x%y);
}

struct FLOAT{
    int A, B;
    FLOAT update(){
        int g=Gcd(A,B);
        return {A/g,B/g};
    }
    FLOAT operator+(const FLOAT&r)const{return (FLOAT){A*r.B+r.A*B, B*r.B}.update();}
    FLOAT operator-(const FLOAT&r)const{return (FLOAT){A*r.B-r.A*B, B*r.B}.update();}
    FLOAT operator*(const FLOAT&r)const{return (FLOAT){A*r.A, B*r.B}.update();}
    FLOAT operator/(const FLOAT&r)const{return (FLOAT){A*r.B, B*r.A}.update();}
    bool operator<(const FLOAT&r){return A*r.B < B*r.A;}
    bool operator==(const FLOAT&r){return A*r.B == B*r.A;}
    bool operator<=(const FLOAT&r){return A*r.B <= B*r.A;}
};
FLOAT f(int x){return {x,1};}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>N>>L;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=L; j++){
            cin>>V[i][j];
            Vsum[i] += V[i][j];
        }
    }
    
    int p[LM];
    for(int i=1; i<=N; i++) p[i]=i;
    
    
    while(1){
        vector<FLOAT> ans;
        FLOAT l={0,1};
        
        for(int I=1; I<=N; I++){
            int i=p[I];
            //printf("%d\n",i);
            
            FLOAT w=f(Vsum[i])/f(N);
            
            if( w <= f(V[i][l.A/l.B+1]) * (f(l.A/l.B+1)-l) ){
                l = l + w / f(V[i][l.A/l.B+1]) ;
                ans.push_back(l);
                continue;
            }
            w = w - f(V[i][l.A/l.B+1]) * (f(l.A/l.B+1)-l);
            l = f(l.A/l.B+1);
            
            //printf("%d %d\n", w.A, w.B);
            
            for(int j=l.A+1; j<=L; j++){
                if(w <= f(V[i][j])){
                    l = l + w/f(V[i][j]);
                    w = {0,1};
                    break;
                }
                l.A++;
                w = w - f(V[i][j]);
            }
           // printf("%d %d\n", l.A, l.B);
            if((FLOAT){0,1} < w) break;
            
            ans.push_back(l);
        }
        
        if(ans.size() == N){
            ans.pop_back();
            for(auto[a,b]:ans) cout<<a<<" "<<b<<'\n';
            for(int i=1; i<=N; i++) cout<<p[i]<<" ";
            return 0;
        }
        
        if(!next_permutation(p+1, p+N+1)) break;
    }
    
    cout<<"FUCK";
}

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