Submission #605332

#	Time	Username	Problem	Language	Result	Execution time	Memory
605332		gagik_2007	Carnival Tickets (IOI20_tickets)	C++17	100 / 100	998 ms	148548 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second

typedef long long ll;
typedef long double ld;

const int INF = 1e9;
ll n, k, m;
vector<ll>mns, mxs, mns_, mxs_;
ll erkaranun[1507][1507];
ll cnt0[1507];
vector<pair<int, int>>d;
vector<int>os[1507], ls[1507];
int os_[1507], ls_[1507];
vector<vector<int>>ans;
vector<int>ap, am;
vector<vector<int>>a;
bool isap[1507];
bool isam[1507];
bool ismx[1507][1507];
bool ismn[1507][1507];
ll mxc[1507];
ll mnc[1507];
int mxi[1507], mni[1507];
ll dp[1507][1507];
ll DP[307][90007];

struct Ket {
	int i, j, val;
	Ket(int ii, int jj, int vl) {
		i = ii;
		j = jj;
		val = vl;
	}
	bool operator<(const Ket& other)const {
		return val < other.val;
	}
	friend ostream& operator<<(ostream& os, Ket val);
};

ostream& operator<<(ostream& os, Ket val) {
	os << val.i << " " << val.j << ": " << val.val << ";  ";
	return os;
}

vector<vector<Ket>>s;

struct Tox{
    int pr,sf,ogut,i;
    Tox(int ii){
        pr=k;
        sf=0;
        i=ii;
        count_ogut();
        for(int j=0;j<pr;j++){
            ismn[i][s[i][j].j]=true;
        }
    }
    void count_ogut(){
        if(pr==0)ogut=-INF;
        else ogut=s[i][m-sf-1].val+s[i][pr-1].val;
    }
    void update(){
        ismn[i][s[i][pr-1].j]=false;
        ismx[i][s[i][m-sf-1].j]=true;
        pr--;
        sf++;
        count_ogut();
    }
    bool operator<(const Tox& other)const{
        return ogut<other.ogut;
    }
};

vector<Ket>sax;
priority_queue<Tox>q;

void give_max(int i, int r) {
	////cout << "-- " << i << " " << r << " " << mxc[i] << endl;
	mxc[i]--;
	for (int j = mxi[i] + 1; j < m; j++) {
		if (ismx[i][j]) {
			////cout << j << endl;
			mxi[i] = j;
			ans[i][j] = r;
			break;
		}
	}
}

void give_min(int i, int r) {
	////cout << "== " << i << " " << r << endl;
	mnc[i]--;
	for (int j = mni[i] + 1; j < m; j++) {
		if (ismn[i][j]) {
			//////cout << j << " ";
			mni[i] = j;
			ans[i][j] = r;
			break;
		}
	}
}

ll find_maximum(int K, vector<vector<int>> x) {
	n = x.size();
	m = x[0].size();
	a=x;
	k=K;
    for (int i = 0; i < n; i++) {
        vector<Ket>v;
        s.push_back(v);
        for (int j = 0; j < m; j++) {
            Ket ket(i, j, x[i][j]);
            s[i].push_back(ket);
        }
        sort(s[i].begin(), s[i].end());
        Tox tox(i);
        q.push(tox);
    }
    for(int i=0;i<n/2*k;i++){
        Tox cur=q.top();
        q.pop();
        cur.update();
        q.push(cur);
    }

    //4-i lucumy
    ans.resize(n);
    for (int i = 0; i < n; i++) {
        ans[i].resize(m, -1);
    }
    mns.push_back(0);
    mxs.push_back(0);
    for (int i = 0; i < n; i++) {
        mni[i] = -1;
        mxi[i] = -1;
        ll mn = INF, mx = 0;
        int mn_ = -1, mx_ = -1;
        for (int j = 0; j < m; j++) {
            Ket ket(i, j, x[i][j]);
            sax.push_back(ket);
            if (x[i][j] < mn) {
                mn_ = j;
            }
            if (x[i][j] > mx) {
                mx_ = j;
            }
            mn = min(mn, x[i][j] * 1ll);
            mx = max(mx, x[i][j] * 1ll);
        }
        mns.push_back(mn);
        mxs.push_back(mx);
        mns_.push_back(mn_);
        mxs_.push_back(mx_);
    }
    sort(sax.begin(), sax.end());
    ll res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ismn[i][j]) {
                res -= x[i][j];
            }
            if (ismx[i][j]) {
                res += x[i][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        bool is_ap = true;
        bool is_am = true;
        for (int j = 0; j < m; j++) {
            if (ismx[i][j]) {
                is_ap = false;
            }
            if (ismn[i][j]) {
                is_am = false;
            }
        }
        if (is_am) {
            am.push_back(i);
            isam[i] = true;
        }
        else if (is_ap) {
            ap.push_back(i);
            isap[i] = true;
        }
        else {
            for (int j = 0; j < m; j++) {
                if (ismx[i][j]) {
                    mxc[i]++;
                }
                if (ismn[i][j]) {
                    mnc[i]++;
                }
            }
        }
    }
    ////cout << "-> " << ap.size() << " " << am.size() << endl;
    //////cout << ap[0] << endl;
    for (int r = 0; r < k; r++) {
        for (int tox : am) {
            give_max(tox, r);
        }
        int cnt = 0;
        for (int tox : ap) {
            give_min(tox, r);
            cnt++;
        }
        int len = m - r - 1;
        for (int tox = 0; tox < n; tox++) {
            if (!isap[tox] && !isam[tox]) {
                if (cnt < n / 2) {
                    give_min(tox, r);
                    if (mnc[tox] == 0) {
                        isam[tox] = true;
                        am.push_back(tox);
                    }
                    cnt++;
                }
                else {
                    give_max(tox, r);
                    if (mxc[tox] == 0) {
                        isap[tox] = true;
                        ap.push_back(tox);
                    }
                }
            }
        }
    }
    allocate_tickets(ans);
    return res;
}

/*
3 1 1 1 2 3

4 4 4 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1
7
4 4 4
5 8 6 9
4 1 5 2
3 6 5 7
8 4 5 9
29
5 5 5
1 2 3 6 5
4 8 5 2 7
9 4 5 8 9
5 6 4 8 4
2 5 1 4 6
69
5 5 4 1 2 3 6 5 4 8 5 2 7 9 4 5 8 9 5 6 4 8 4 2 5 1 4 6
4 4 4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
4 4 4 1 2 1 2 1 2 1 2 3 4 3 4 3 4 3 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
4 4 4 4 4 4 5 4 4 4 5 4 4 4 5 4 4 4 5
4 4 4 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

5

4 4 2
1 5 6 2
2 9 4 8
6 4 2 5
3 4 7 8
23
0 1 -1 -1
-1 0 -1 1
1 0 -1 -1
1 -1 -1 0



*/

Compilation message (stderr)

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:213:13: warning: unused variable 'len' [-Wunused-variable]
  213 |         int len = m - r - 1;
      |             ^~~

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