oj.uz

Submission #120566

# Submission time Handle Problem Language Result Execution time Memory
120566 2019-06-25T01:28:18 Z errorgorn Naan (JOI19_naan) C++14
0 / 100
 3 ms 512 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct fraction{
    long long a,b;
    fraction(){
        a=0;
        b=1;
    }
    fraction (long long i, long long _a, long long _b){
        a=_a;
        b=_b;
        a+=i*b;
    }
    long long whole(){
        return a/b;
    }
    bool operator < (fraction *i){
        if (i->b==0){
            return true;
        }
        if (whole()!=i->whole()){
            return whole()<i->whole();
        }
        else{
            return (a-(b*whole()))*i->b<(i->a-(i->b*whole()))*b;
        }
    }
    void init_inf(){
        a=1;
        b=0;
    }
};
int n,l;
int arr[2005][2005];
fraction *split[2005][2005];
vector<int> rem;
int perm[2005];
int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&l);
    long long total,curr_total;
    long long inc,val;
    int pointer;
    for (int x=1;x<=n;x++){
        total=0;
        for (int y=0;y<l;y++){
            scanf("%d",&arr[x][y]);
            arr[x][y]*=n;
            total+=arr[x][y];
        }
        inc=total/n;
        val=inc;
        pointer=0;
        curr_total=0;
        while (val!=total){
            while (val<curr_total+arr[x][pointer]){
                split[x][val/inc]=new fraction(pointer, val-curr_total,arr[x][pointer]);
                val+=inc;
            }
            curr_total+=arr[x][pointer];
            pointer++;
        }
        rem.push_back(x);
    }
    pointer=1;
    int best_index;
    int index;
    while (rem.size()>1){
        best_index=-1;
        for (int x=0;x<rem.size();x++){
            index=rem[x];
            if (best_index==-1 || split[index][pointer]<split[best_index][pointer]){
                best_index=index;
            }
        }
        printf("%lld %lld\n",split[best_index][pointer]->a,split[best_index][pointer]->b);
        rem.erase(find(rem.begin(),rem.end(),best_index));
        perm[pointer]=best_index;
        pointer++;
    }
    for (int x=1;x<n;x++){
        printf("%d ",perm[x]);
    }
    printf("%d\n",rem[0]);
}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:72:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int x=0;x<rem.size();x++){
                      ~^~~~~~~~~~~
naan.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&l);
     ~~~~~^~~~~~~~~~~~~~
naan.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&arr[x][y]);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Not a fair distribution.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 3 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 3 ms 412 KB Output is correct
19 Correct 3 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 3 ms 428 KB Output is correct
23 Incorrect 2 ms 512 KB Not a fair distribution.
24 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Not a fair distribution.
2 Halted 0 ms 0 KB -