Submission #1283274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283274		edo	Carnival Tickets (IOI20_tickets)	C++20	0 / 100	1 ms	344 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;
using ll   = long long;
using vi   = vector<int>;
using vll  = vector<ll>;
using vvi  = vector<vi>;
using vvll = vector<vll>;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using ui    = unsigned int;
using ull   = unsigned long long;
using pui   = pair<ui,ui>;
using pull  = pair<ull,ull>;

template<typename T>
using vc = std::vector<T>;


#define YES cout << "YES\n"
#define NO  cout << "NO\n"
#define yes cout << "yes\n"
#define no  cout << "no\n"
#define Yes cout << "Yes\n"
#define No  cout << "No\n"

template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.first), sc(p.second); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }


template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.first); cout << ' '; _pt(p.second);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}


template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n)            for (int i=0; i<(n); ++i)
#define FOR2(i,n)          for (int i=0; i<(n); ++i)
#define FOR3(i,l,r)        for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k)      for (int i=(l); i<(r); i+=(k))
#define FOR(...)           GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n)            for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n)          for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r)        for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k)      for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...)           GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c)   (c).begin(), (c).end()
#define allr(c)  (c).rbegin(), (c).rend()
#define eb       emplace_back
#define mp       make_pair
#define mt       make_tuple
#define fi       first
#define se       second
#define pb       push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")

ll find_maximum(int k, vc<vc<int>> x) {
    int N = sz(x);
    int M = sz(x.at(0));

    vc<ll> f0(N);
    vc<vc<ll>> d(N, vc<ll>(k));

    FOR(N) {
        FOR(j, k) 
            f0.at(i) -= x.at(i).at(j);
        FOR(j, k) 
            d.at(i).at(j) = x.at(i).at(M - 1 - j) + x.at(i).at(k - 1 - j);
    }

    vc<ll> allD;

    FOR(N)
        FOR(j, k)
            allD.pb(d.at(i).at(j));

    sort(allr(allD));

    ll sum = 0;
    int need = k * N / 2;
    FOR(need) 
        sum += allD.at(i);

    ll trash = allD.at(need - 1);

    int cnt = 0;
    vc<int> g(N);
    FOR(N) 
        FOR(j, k) {
            if(d.at(i).at(j) > trash) {
                g.at(i)++;
                cnt++;
            }
        }

    FOR(N) 
        FOR(j, k) {
            if(d.at(i).at(j) == trash && cnt < need) {
                g.at(i)++;
                cnt++;
            }
        }
        
    ll tot = 0;
    FOR(N) 
        tot += f0.at(i);
    tot += sum;

    vc<vc<int>> A(N, vc<int>(k, 0));
    vc<int> rem = g;
    FOR(r, k) {
        vc<pii> tmp;
        FOR(N)
            tmp.pb({rem.at(i), i});

        sort(allr(tmp));
        FOR(j, N >> 1) {
            int i = tmp.at(j).se;
            A.at(i).at(r) = 1;
            rem.at(i)--;
        }
    }

    vc<vc<int>> arr(N, vc<int>(M, -1));
    FOR(N) {
        vc<int> upper;
        FOR(j, M - g.at(i), M) 
            upper.pb(j);

        vc<int> lower;
        FOR(j, k - g.at(i)) 
            lower.pb(j);

        int u = 0, l = 0;
        FOR(r, k) {
            if(A.at(i).at(r) == 1) {
                arr.at(i).at(upper.at(u++)) = r;
            }
            else {
                arr.at(i).at(lower.at(l++)) = r;
            }
        }
    }


    allocate_tickets(arr);
	return 1;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10