oj.uz

Submission #566930

# Submission time Handle Problem Language Result Execution time Memory
566930 2022-05-23T06:30:38 Z 600Mihnea Naan (JOI19_naan) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct Fraction {
  ll a;
  ll b;

  Fraction(ll a, ll b) : a(a), b(b) {

  }
};

ld getld(Fraction fr) {
  return (ld)fr.a/(ld)fr.b;
}

bool operator < (Fraction First,Fraction Second) {
  return (ld)First.a/First.b<(ld)Second.a/Second.b;  /// may be a bug here
}

Fraction operator + (Fraction First,ll Second) {
  return Fraction(First.a+Second*First.b, First.b);
}

Fraction operator + (ll Second, Fraction First) {
  return Fraction(First.a+Second*First.b, First.b);
}


Fraction operator - (Fraction First,ll Second) {
  return Fraction(First.a-Second*First.b, First.b);
}

Fraction operator - (ll Second,Fraction First) {
  return Fraction(-First.a+Second*First.b, First.b);
}

Fraction operator * (Fraction First,ll Second) {
  return Fraction(First.a*Second, First.b);
}

Fraction operator * (ll Second, Fraction First) {
  return Fraction(First.a*Second, First.b);
}


signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  int People,n;
  cin>>People>>n;
  vector<vector<int>> a(People,vector<int> (n));
  vector<vector<Fraction>> splitPoint(People,vector<Fraction>(People,Fraction(0,1)));

  for (int i=0;i<People;i++) {
    for (int j=0;j<n;j++) {
      cin>>a[i][j];
    }
  }

  for (int Person=0;Person<People;Person++) {
    ///cout<<"Person = "<<Person<<"\n";
    vector<int> elements=a[Person];
    ll totalSum=0;
    for (auto &x:elements) {
      totalSum+=x;
    }
    int done=0;
    ll currentSum=0;
    Fraction din(0, 1);
    for (int j=0;j<People;j++) {
      /// compute splitPoint[Person][j]
      /// the first having <= (j + 1) * totalSum / People
    ///  cout<<j<<" = "<<j<<", din = "<<getld(din)<<" "<<(ld)j/7<<"\n";
      Fraction want((j+1)*totalSum, People);
     /// cout<<"want = "<<getld(want)<<"\n\n";
      assert(done<n);
      while (Fraction(currentSum+elements[done],1)<want){
        assert(done<n);
        Fraction FF=Fraction(currentSum+elements[done], 1), SS=want;
       /// cout<<"\t\t\t\t"<<fixed<<setprecision(6)<<getld(FF)<<" "<<getld(SS)<<"\n";
       /// cout<<fixed<<setprecision(6)<<(ld)FF.a/(ld)FF.b<<" vs "<<(ld)SS.a/(ld)SS.b<<"\n";
        currentSum+=elements[done++];
        din=Fraction(0,1);
        assert(done<n);
      }
      assert(done<n);
    ///  cout<<j<<" : "<<done<<"\n";
      /// currentSum + elements[done] * x = want
      Fraction dif=want-currentSum;
      /// elements[done] * x = dif
      Fraction x(dif.a,dif.b*elements[done]);
      splitPoint[Person][j]=done+x;

     /// cout<<"lol : "<<fixed<<setprecision(6)<<getld(splitPoint[Person][j])<<"\n";
      din=x;

      /// x = x - din
      continue;
      //while (Fraction(currentSum+elements[done])<Fraction((j+1)*totalSum,People)) {
      //  assert(done<n);
     //   currentSum+=elements[done++];
      //}
      assert(done<n);
      /// currentSum + elements[done] * x = (j + 1) * totalSum / People
      /// elements[done] * x = ((j + 1) * totalSum - currentSum * People) / People
      /// x = ((j + 1) * totalSum - currentSum * People) / (elements[done] * People)
    ///  Fraction x((j + 1) * totalSum - currentSum * People, elements[done] * People);
    }
    if (0) {
      assert(Person==0);
      cout<<"good \n";
      exit(0);
    }
  }

  vector<bool> valid(People,1);

  vector<int> guys;

  for (int ch=0;ch<People;ch++) {
    int sol=-1;
    for (int i=0;i<People;i++){
      if (valid[i]) {
        if (sol==-1) {
          sol=i;
        }else{
          if (splitPoint[i][ch]<splitPoint[sol][ch]) {
            sol=i;
          }
        }
      }
    }
    assert(sol!=-1);
    valid[sol]=0;
    if (ch!=People-1) {
      cout<<splitPoint[sol][ch].a<<"/"<<splitPoint[sol][ch].b<<" ";
    }
    guys.push_back(sol);
  }
  cout<<"\n";
  for (auto &Guy:guys) {
    cout<<Guy+1<<" ";
  }
  cout<<"\n";

  return 0;
  for (auto &v:splitPoint) {
    for (auto &fr:v) {
      cout<<fr.a<<"/"<<fr.b<<" ";
    }
    cout<<"\n";
  }

}

Compilation message

naan.cpp: In function 'int main()':
naan.cpp:84:18: warning: variable 'FF' set but not used [-Wunused-but-set-variable]
   84 |         Fraction FF=Fraction(currentSum+elements[done], 1), SS=want;
      |                  ^~
naan.cpp:84:61: warning: variable 'SS' set but not used [-Wunused-but-set-variable]
   84 |         Fraction FF=Fraction(currentSum+elements[done], 1), SS=want;
      |                                                             ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Expected integer, but "22/8" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Expected integer, but "5696/10" found
2 Halted 0 ms 0 KB -

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Expected integer, but "22/8" found
2 Halted 0 ms 0 KB -