Submission #1170447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170447		Zbyszek99	Naan (JOI19_naan)	C++20	29 / 100	4094 ms	128792 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
{
    ll a,b;
    bool operator<(const frac& other) const 
    {
        return (__int128_t)a * (__int128_t)other.b < (__int128_t)other.a * (__int128_t)b;
    }
    bool operator<=(const frac& other)
    {
        return (__int128_t)a * (__int128_t)other.b <= (__int128_t)other.a * (__int128_t)b;
    }
    bool operator>(const frac& other)
    {
        return (__int128_t)a * (__int128_t)other.b > (__int128_t)other.a * (__int128_t)b;
    }
    bool operator>=(const frac& other)
    {
        return (__int128_t)a * (__int128_t)other.b >= (__int128_t)other.a * (__int128_t)b;
    }
    bool operator==(const frac& other)
    {
        return (__int128_t)a * (__int128_t)other.b == (__int128_t)other.a * (__int128_t)b;
    }
    frac operator+(const frac& other)
    {
        __int128_t a2 = (__int128_t)a * (__int128_t)other.b + (__int128_t)other.a * (__int128_t)b;
        __int128_t b2 = (__int128_t)b * (__int128_t)other.b;
        return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
    }
    frac operator-(const frac& other)
    {
        __int128_t a2 = (__int128_t)a * (__int128_t)other.b - (__int128_t)other.a * (__int128_t)b;
        __int128_t b2 = (__int128_t)b * (__int128_t)other.b;
        return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
    }
    frac operator*(const frac& other)
    {
        __int128_t a2 = (__int128_t)a * (__int128_t)other.a;
        __int128_t b2 = (__int128_t)b * (__int128_t)other.b;
        return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
    }
    frac operator/(const frac& other)
    {
        __int128_t a2 = (__int128_t)a * (__int128_t)other.b;
        __int128_t b2 = (__int128_t)b * (__int128_t)other.a;
        return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
    }
};

frac V[2000];
frac wym;
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[j] = {a,1};
        }
        wym = {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[j] >= wym)
            {
                frac cur2 = {j,1};
                frac def_poz = {j+1,1};
                while(true)
                {
                    if((def_poz - cur2) * V[j] + cur_sum >= wym)
                    {
                        frac end_poz = cur2 + (wym - cur_sum)/V[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[j];
                        break;
                    }
                }
            }
            else
            {
                cur_sum = cur_sum + V[j];
            }
        }
    }
    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 << " "; 
}  

Compilation message (stderr)

naan.cpp: In member function 'frac frac::operator+(const frac&)':
naan.cpp:57:20: warning: narrowing conversion of '(a2 / std::__gcd<__int128>(std::abs(a2), std::abs(b2)))' from '__int128' to 'long long int' [-Wnarrowing]
   57 |         return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~
naan.cpp:57:48: warning: narrowing conversion of '(b2 / std::__gcd<__int128>(std::abs(a2), std::abs(b2)))' from '__int128' to 'long long int' [-Wnarrowing]
   57 |         return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
      |                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
naan.cpp: In member function 'frac frac::operator-(const frac&)':
naan.cpp:63:20: warning: narrowing conversion of '(a2 / std::__gcd<__int128>(std::abs(a2), std::abs(b2)))' from '__int128' to 'long long int' [-Wnarrowing]
   63 |         return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~
naan.cpp:63:48: warning: narrowing conversion of '(b2 / std::__gcd<__int128>(std::abs(a2), std::abs(b2)))' from '__int128' to 'long long int' [-Wnarrowing]
   63 |         return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
      |                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
naan.cpp: In member function 'frac frac::operator*(const frac&)':
naan.cpp:69:20: warning: narrowing conversion of '(a2 / std::__gcd<__int128>(std::abs(a2), std::abs(b2)))' from '__int128' to 'long long int' [-Wnarrowing]
   69 |         return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~
naan.cpp:69:48: warning: narrowing conversion of '(b2 / std::__gcd<__int128>(std::abs(a2), std::abs(b2)))' from '__int128' to 'long long int' [-Wnarrowing]
   69 |         return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
      |                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~
naan.cpp: In member function 'frac frac::operator/(const frac&)':
naan.cpp:75:20: warning: narrowing conversion of '(a2 / std::__gcd<__int128>(std::abs(a2), std::abs(b2)))' from '__int128' to 'long long int' [-Wnarrowing]
   75 |         return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
      |                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~
naan.cpp:75:48: warning: narrowing conversion of '(b2 / std::__gcd<__int128>(std::abs(a2), std::abs(b2)))' from '__int128' to 'long long int' [-Wnarrowing]
   75 |         return {a2 / __gcd(abs(a2),abs(b2)),b2 / __gcd(abs(a2),abs(b2))};
      |                                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~

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