Submission #1170439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170439		Zbyszek99	Naan (JOI19_naan)	C++20	29 / 100	2318 ms	161228 KiB

naan

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct frac
{
    __int128_t a,b;
    bool operator<(const frac& other) const 
    {
        return a * other.b < other.a * b;
    }
    bool operator<=(const frac& other)
    {
        return a * other.b <= other.a * b;
    }
    bool operator>(const frac& other)
    {
        return a * other.b > other.a * b;
    }
    bool operator>=(const frac& other)
    {
        return a * other.b >= other.a * b;
    }
    bool operator==(const frac& other)
    {
        return a * other.b == other.a * b;
    }
    frac operator+(const frac& other)
    {
        ll a2 = a * other.b + other.a * b;
        ll b2 = b * other.b;
        return {a2 / __gcd(a2,b2),b2 / __gcd(a2,b2)};
    }
    frac operator-(const frac& other)
    {
        ll a2 = a * other.b - other.a * b;
        ll b2 = b * other.b;
        return {a2 / __gcd(abs(a2),b2),b2 / __gcd(abs(a2),b2)};
    }
    frac operator*(const frac& other)
    {
        ll a2 = a * other.a;
        ll b2 = b * other.b;
        return {a2 / __gcd(a2,b2),b2 / __gcd(a2,b2)};
    }
    frac operator/(const frac& other)
    {
        ll a2 = a * other.b;
        ll b2 = b * other.a;
        return {a2 / __gcd(a2,b2),b2 / __gcd(a2,b2)};
    }
};

frac V[2000][2000];
frac wym[2000];
vector<pair<frac,frac>> segs[2000];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,l;
    cin >> n >> l;
    rep(i,n)
    {
        int sum = 0;
        rep(j,l)
        {
            int a;
            cin >> a;
            sum += a;
            V[i][j] = {a,1};
        }
        wym[i] = {sum,n};
        frac cur_poz = {0,1};
        frac cur_sum = {0,1};
        rep(j,l)
        {
            // cout << cur_sum.a << "/" << cur_sum.b << " cur_sum\n";
            // cout << wym[i].a << "/" << wym[i].b << " wym\n\n";
            if(cur_sum + V[i][j] >= wym[i])
            {
                frac cur2 = {j,1};
                frac def_poz = {j+1,1};
                while(true)
                {
                    if((def_poz - cur2) * V[i][j] + cur_sum >= wym[i])
                    {
                        frac end_poz = cur2 + (wym[i] - cur_sum)/V[i][j];
                      //  cout << end_poz.a << "/" << end_poz.b << " end_poz\n";
                        segs[i].pb({cur_poz,end_poz});
                        cur_poz = end_poz;
                        cur2 = end_poz;
                        cur_sum = {0,1};
                    }
                    else
                    {
                        cur_sum = cur_sum + (def_poz - cur2) * V[i][j];
                        break;
                    }
                }
            }
            else
            {
                cur_sum = cur_sum + V[i][j];
            }
        }
    }
  //  rep(i,n)
  ///  {
  //      forall(it,segs[i])
  //      {
  //          cout << it.ff.a << "/" << it.ff.b << " " << it.ss.a << "/" << it.ss.b << "\n";
  //      }
  //      cout << "\n";
  //  }
    rep(i,n)
    {
        reverse(all(segs[i]));
    }
    vi P;
    vector<frac> end_vect;
    rep(i,n)
    {
        pair<frac,int> min_end = {{(__int128_t)1e18,1},1};
        rep(j,n)
        {
            if(siz(segs[j]) == 0) continue;
            min_end = min(min_end,{segs[j].back().ss,j});
        }
        P.pb(min_end.ss+1);
        end_vect.pb(min_end.ff);
        segs[min_end.ss] = {};
        rep(j,n)
        {
            if(siz(segs[j]) != 0) segs[j].pop_back();
        }
    }
    rep(i,n-1) cout << (ll)end_vect[i].a << " " << (ll)end_vect[i].b << " ";
    cout << "\n";
    forall(it,P) cout << it << " "; 
}  

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