oj.uz

Submission #651187

# Submission time Handle Problem Language Result Execution time Memory
651187 2022-10-17T22:22:22 Z tvladm2009 Naan (JOI19_naan) C++14
29 / 100
 30 ms 7884 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 / (ld)First.b <= (ld)Second.a / (ld)Second.b;
}

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

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

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

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

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

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

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.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++) {
    ll totalSum = 0;
    for (auto& x : a[Person]) {
      totalSum += x;
    }
    int done = 0;
    ll currentSum = 0;
    Fraction fromLast(0, 1);
    for (int j = 0; j < People; j++) {
      Fraction want((j + 1) * totalSum, People);
      while (Fraction(currentSum + a[Person][done], 1) < want) {
        currentSum += a[Person][done++];
        fromLast = Fraction(0, 1);
      }
      Fraction dif = want - currentSum;
      Fraction x(dif.a, dif.b * a[Person][done]);
      splitPoint[Person][j] = done + x;
      fromLast = x;
    }
  }

  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[ch][sol]) {
            sol = i;
          }
        }
      }
    }
    valid[sol] = 0;
    if (ch != People - 1) {
      cout << splitPoint[sol][ch].a << " " << splitPoint[sol][ch].b << "\n";
    }
    guys.push_back(sol);
  }
  for (auto &Guy : guys) {
    cout << Guy + 1 << " ";
  }
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 328 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 340 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 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 332 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 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 396 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 332 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 404 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 1 ms 328 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 340 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 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 332 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 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 396 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 2 ms 332 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 404 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 212 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Incorrect 30 ms 7884 KB X_i is not increasing
44 Halted 0 ms 0 KB -