Submission #1170418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170418		owieczka	Naan (JOI19_naan)	C++20	29 / 100	257 ms	67408 KiB

naan

#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct ulamek
{
   ll l;
   ll m;
};

ulamek operator+(const ulamek& l, const ulamek& p)
{
   ll g = gcd(l.m, p.m);
   ll lm = l.m / g;
   ll pm = p.m / g;
   return {l.l*pm + p.l*lm, l.m*pm};
}
ulamek operator-(const ulamek& l, const ulamek& p)
{
   ll g = gcd(l.m, p.m);
   ll lm = l.m / g;
   ll pm = p.m / g;
   return {l.l*pm - p.l*lm, l.m*pm};
}
ulamek operator*(const ulamek& l, const ulamek& p)
{
   return {l.l*p.l, l.m*p.m};
}
ulamek operator/(const ulamek& l, const ulamek& p)
{
   return {l.l*p.m, l.m*p.l};
}
bool operator<(const ulamek& l, const ulamek& p)
{
   return l.l * p.m < p.l * l.m;
}

ulamek V[2'002][2'002];
ulamek podz[2'002][2'002];
ulamek needs[2'002];
bool o[2'002];
ll perm[2'002];
ulamek fin[2'002];

int main()
{
   ios::sync_with_stdio(0); cin.tie(0);
   ll n, l;
   cin >> n >> l;
   for (ll i = 0; i < n; i++)
   {
      needs[i].m = n;
      for(ll j = 0; j < l; j++)
      {
         cin >> V[i][j].l;
         V[i][j].m = 1;
         needs[i].l += V[i][j].l;
      }
      ulamek h = {0, 1};
      ll j = 0;
      for (ll id = 0; id < n; id++)
      {
         while (h + V[i][j] < needs[i])
         {
            h = h + V[i][j++];
         }
         ulamek r = needs[i] - h;
         ulamek x = r / V[i][j];
         podz[i][id] = x + ulamek{j, 1};
         // cout << podz
         h = ulamek{0, 1}-r;
      }
   }
   for (ll i = 0; i < n; i++)
   {
      ulamek m = {1, 0};
      ll id = -1;
      for (ll j = 0; j < n; j++)
      {
         if (o[j])continue;
         if (podz[j][i] < m)
         {
            m = podz[j][i];
            id = j;
         }
      }
      o[id] = 1;
      perm[i] = id;
      // fin[i] = m;
      if (i != n - 1)cout << m.l << ' ' << m.m << '\n';
   }
   for (ll i = 0; i < n; i++)
   {
      cout << perm[i] + 1 << ' ';
   }
   
}

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