제출 #1170451

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170451		owieczka	Naan (JOI19_naan)	C++20	100 / 100	2193 ms	125948 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)
{
   ulamek ans = {l.l * p.m + p.l * l.m, p.m * l.m};
   ll g = gcd(ans.l, ans.m);
   ans.l /= g;
   ans.m /= g;
   return ans;
}
ulamek operator-(const ulamek& l, const ulamek& p)
{
   ulamek ans = {l.l * p.m - p.l * l.m, p.m * l.m};
   ll g = gcd(ans.l, ans.m);
   ans.l /= g;
   ans.m /= g;
   return ans;
}
ulamek operator*(const ulamek& l, const ulamek& p)
{
   ulamek ans = {l.l*p.l, l.m*p.m};
   ll g = gcd(ans.l, ans.m);
   ans.l /= g;
   ans.m /= g;
   return ans;
}
ulamek operator/(const ulamek& l, const ulamek& p)
{
   ulamek ans = {l.l*p.m, l.m*p.l};
   ll g = gcd(ans.l, ans.m);
   ans.l /= g;
   ans.m /= g;
   return ans;
}
bool operator<(const ulamek& l, const ulamek& p)
{
   __int128_t a = l.l;
   __int128_t b = p.l;
   __int128_t c = l.m;
   __int128_t d = p.m;
   return a * d < b * c;
}

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: 71 / 71