Submission #596184

#	Time	Username	Problem	Language	Result	Execution time	Memory
596184		Red_Inside	Carnival Tickets (IOI20_tickets)	C++17	25 / 100	1309 ms	104796 KiB

tickets

#include "tickets.h"

#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=1e6+10,LOG=17,mod=998244353;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const int inf=2e9;
#define y1 yy
#define prev pre
#define pii pair <int, int>

ll mni[maxn], mxi[maxn];
ll mx[maxn], mn[maxn];

bool cmp(pii a, pii b)
{
	return a.f > b.f;
}


long long find_maximum(int k, vector <vector <int> > a)
{
	vector <vector <int> > use, mark;
	int n = a.size();
	int m = a[0].size();
	use = a;
	forn(0, i, n-1) forn(0, j, m-1) use[i][j] = -1;
	ll ret = 0;
	vector <pair <ll, pii> > vec;
	forn(0, i, n-1)
	{
		forn(0, j, m-1)
		{
			vec.pb({a[i][j], {i, j}});
		}
	}
	sort(all(vec));
	reverse(all(vec));
	set <pii> st;
	forn(0, i, k-1)
	{
		st.insert({0, i});
	}
	mark = use;
	FOR(0, i, vec.size() / 2)
	{
		mark[vec[i].s.f][vec[i].s.s] = 1;
	}
	forn(0, i, n-1)
	{
		set <pii> nw;
		forn(0, j, m-1)
		{
			if(mark[i][j] == 1)
			{
//				cout << i << " " << j << " " << a[i][j] << endl;
				use[i][j] = st.begin()->s;
				pii temp = *st.begin();
				st.erase(*st.begin());
				temp.f++;
				ret += a[i][j];
				nw.insert(temp);
			}
			else
			{
				use[i][j] = st.rbegin()->s;
				pii temp = *st.rbegin();
				st.erase(*st.rbegin());
				temp.f--;
				ret -= a[i][j];
				nw.insert(temp);
			}
		}
		st = nw;
	}
/*	forn(0, i, n-1)
	{
		forn(0, j, m-1) if(mark[i][j] == 1) cout << 1 << ' '; else cout << 0 << " ";
		cout << endl;
	}*/
	vector <vector <int> > vec2;
	vec2.assign(k, {});
	forn(0, i, n-1)
	{
		forn(0, j, m-1)
		{
			vec2[use[i][j]].pb(a[i][j]);
		}
	}
	ll ret2 = 0;
	forn(0, i, k-1)
	{
		sort(all(vec2[i]));
		FOR(0, j, vec2[i].size() / 2)
		{
			ret2 -= vec2[i][j];
		}
		FOR(vec2[i].size() / 2, j, vec2[i].size())
		{
			ret2 += vec2[i][j];
		}
	}
	if(ret2 != ret)
	{
		cout << "ERROR!!!\n";
	}
	allocate_tickets(use);
	return ret;
}

Compilation message (stderr)

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
   65 |  FOR(0, i, vec.size() / 2)
      |         ~~~~~~~~~~~~~~~~~              
tickets.cpp:65:2: note: in expansion of macro 'FOR'
   65 |  FOR(0, i, vec.size() / 2)
      |  ^~~
tickets.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  114 |   FOR(0, j, vec2[i].size() / 2)
      |          ~~~~~~~~~~~~~~~~~~~~~         
tickets.cpp:114:3: note: in expansion of macro 'FOR'
  114 |   FOR(0, j, vec2[i].size() / 2)
      |   ^~~
tickets.cpp:11:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 | #define FOR(i, j, n) for(int j = i; j < n; ++j)
......
  118 |   FOR(vec2[i].size() / 2, j, vec2[i].size())
      |                           ~~~~~~~~~~~~~~~~~
tickets.cpp:118:3: note: in expansion of macro 'FOR'
  118 |   FOR(vec2[i].size() / 2, j, vec2[i].size())
      |   ^~~

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