제출 #1170406

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170406		owieczka	Naan (JOI19_naan)	C++20	29 / 100	250 ms	67464 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];
int perm[2'002];
ulamek fin[2'002];

int main()
{
   ios::sync_with_stdio(0); cin.tie(0);
   int n, l;
   cin >> n >> l;
   for (int i = 0; i < n; i++)
   {
      needs[i].m = n;
      for(int 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};
      int j = 0;
      for (int 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 (int i = 0; i < n; i++)
   {
      ulamek m = {1, 0};
      int id = -1;
      for (int 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 (int i = 0; i < n; i++)
   {
      cout << perm[i] + 1 << ' ';
   }
   
}

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