#include "tickets.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
long long find_maximum(int k, std::vector<std::vector<int>> x) {
ll N = x.size();
ll M = x[0].size();
{
vector<std::tuple<ll,ll,ll>> data;
rep(i,0,N){
rep(j,0,M) data.pb(mtp(x[i][j],i,j));
}
sort(all(data));
ll ans = 0;
ll mid = N*M/2;
vii left(N), right(N);
rep(i,0,N*M){
ll val, I,J; std::tie(val, I,J) = data[i];
if(left[I].size() < k) left[I].pb(J);
}
per(i,N*M-1,0){
ll val, I,J; std::tie(val, I,J) = data[i];
if(right[I].size() < k) right[I].pb(J);
}
vii use_left(N), use_right(N);
ll goal = N*k/2;
ll current = 0;
std::priority_queue<pii> que;
rep(i,0,N){
reverse(all(right[i]));
use_left[i] = left[i];
que.push(mp(x[i][right[i].back()]+x[i][left[i].back()], i));
}
/*rep(i,0,N){
cout << "! " << i << ln;
for(auto el: left[i]) cout << el << " ";
cout << ln;
for(auto el: use_right[i]) cout << el << " ";
cout << ln;
}*/
while(current < goal){
auto el = que.top(); que.pop();
ll i = el.second;
use_left[i].pop_back();
use_right[i].pb(right[i].back());
right[i].pop_back();
current++;
if(right[i].empty() || use_left[i].empty()) continue;
que.push(mp(x[i][right[i].back()]+x[i][use_left[i].back()], i));
}
vector<vector<int>> allocate(N,vector<int>(M,-1));
{
data.clear();
rep(i,0,N){
for(auto el: use_left[i]) data.pb(mtp(x[i][el],i,el));
for(auto el: use_right[i]) data.pb(mtp(x[i][el],i,el));
}
sort(all(data));
ll ans = 0;
ll mid = N*k/2;
vii left2(N), right2(N);
rep(i,0,mid){
ll val, I,J; std::tie(val, I,J) = data[i];
left2[I].pb(J);
}
rep(i,mid,N*k){
ll val, I,J; std::tie(val, I,J) = data[i];
right2[I].pb(J);
}
use_left = left2;
use_right = right2;
}
vector<pii> cnt(k);
rep(i,0,k) cnt[i] = mp(0,i);
rep(i,0,N){
sort(all(cnt));
ll idx = 0;
for(auto el: use_left[i]){
allocate[i][el] = cnt[idx].second;
cnt[idx].first++;
idx++;
ans -= x[i][el];
}
for(auto el: use_right[i]){
allocate[i][el] = cnt[idx].second;
cnt[idx].first--;
idx++;
ans += x[i][el];
}
}
allocate_tickets(allocate);
return ans;
}
}
Compilation message
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:37:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | if(left[I].size() < k) left[I].pb(J);
| ~~~~~~~~~~~~~~~^~~
tickets.cpp:41:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | if(right[I].size() < k) right[I].pb(J);
| ~~~~~~~~~~~~~~~~^~~
tickets.cpp:81:7: warning: unused variable 'ans' [-Wunused-variable]
81 | ll ans = 0;
| ^~~
tickets.cpp:33:6: warning: unused variable 'mid' [-Wunused-variable]
33 | ll mid = N*M/2;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
624 KB |
Output is correct |
5 |
Correct |
26 ms |
4280 KB |
Output is correct |
6 |
Correct |
619 ms |
116684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
664 KB |
Output is correct |
5 |
Correct |
26 ms |
6100 KB |
Output is correct |
6 |
Correct |
764 ms |
141076 KB |
Output is correct |
7 |
Correct |
756 ms |
145992 KB |
Output is correct |
8 |
Correct |
4 ms |
1104 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
7 ms |
1872 KB |
Output is correct |
13 |
Correct |
24 ms |
5460 KB |
Output is correct |
14 |
Correct |
29 ms |
5792 KB |
Output is correct |
15 |
Correct |
805 ms |
168480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
4 ms |
896 KB |
Output is correct |
5 |
Correct |
39 ms |
8904 KB |
Output is correct |
6 |
Correct |
5 ms |
1588 KB |
Output is correct |
7 |
Correct |
9 ms |
2224 KB |
Output is correct |
8 |
Correct |
1149 ms |
184220 KB |
Output is correct |
9 |
Correct |
1020 ms |
174040 KB |
Output is correct |
10 |
Correct |
1002 ms |
169736 KB |
Output is correct |
11 |
Correct |
1085 ms |
181584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
664 KB |
Output is correct |
3 |
Correct |
3 ms |
664 KB |
Output is correct |
4 |
Correct |
2 ms |
664 KB |
Output is correct |
5 |
Correct |
2 ms |
760 KB |
Output is correct |
6 |
Correct |
3 ms |
792 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
768 KB |
Output is correct |
10 |
Correct |
4 ms |
840 KB |
Output is correct |
11 |
Correct |
3 ms |
792 KB |
Output is correct |
12 |
Correct |
3 ms |
920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
664 KB |
Output is correct |
3 |
Correct |
3 ms |
664 KB |
Output is correct |
4 |
Correct |
2 ms |
664 KB |
Output is correct |
5 |
Correct |
2 ms |
760 KB |
Output is correct |
6 |
Correct |
3 ms |
792 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
768 KB |
Output is correct |
10 |
Correct |
4 ms |
840 KB |
Output is correct |
11 |
Correct |
3 ms |
792 KB |
Output is correct |
12 |
Correct |
3 ms |
920 KB |
Output is correct |
13 |
Correct |
27 ms |
5084 KB |
Output is correct |
14 |
Correct |
23 ms |
5316 KB |
Output is correct |
15 |
Correct |
29 ms |
7108 KB |
Output is correct |
16 |
Correct |
35 ms |
9504 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
2 ms |
788 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
34 ms |
6588 KB |
Output is correct |
21 |
Correct |
32 ms |
6944 KB |
Output is correct |
22 |
Correct |
37 ms |
8340 KB |
Output is correct |
23 |
Correct |
33 ms |
8820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
980 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
624 KB |
Output is correct |
11 |
Correct |
26 ms |
4280 KB |
Output is correct |
12 |
Correct |
619 ms |
116684 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
2 ms |
664 KB |
Output is correct |
17 |
Correct |
26 ms |
6100 KB |
Output is correct |
18 |
Correct |
764 ms |
141076 KB |
Output is correct |
19 |
Correct |
756 ms |
145992 KB |
Output is correct |
20 |
Correct |
4 ms |
1104 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
212 KB |
Output is correct |
24 |
Correct |
7 ms |
1872 KB |
Output is correct |
25 |
Correct |
24 ms |
5460 KB |
Output is correct |
26 |
Correct |
29 ms |
5792 KB |
Output is correct |
27 |
Correct |
805 ms |
168480 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
212 KB |
Output is correct |
31 |
Correct |
4 ms |
896 KB |
Output is correct |
32 |
Correct |
39 ms |
8904 KB |
Output is correct |
33 |
Correct |
5 ms |
1588 KB |
Output is correct |
34 |
Correct |
9 ms |
2224 KB |
Output is correct |
35 |
Correct |
1149 ms |
184220 KB |
Output is correct |
36 |
Correct |
1020 ms |
174040 KB |
Output is correct |
37 |
Correct |
1002 ms |
169736 KB |
Output is correct |
38 |
Correct |
1085 ms |
181584 KB |
Output is correct |
39 |
Correct |
0 ms |
300 KB |
Output is correct |
40 |
Correct |
2 ms |
664 KB |
Output is correct |
41 |
Correct |
3 ms |
664 KB |
Output is correct |
42 |
Correct |
2 ms |
664 KB |
Output is correct |
43 |
Correct |
2 ms |
760 KB |
Output is correct |
44 |
Correct |
3 ms |
792 KB |
Output is correct |
45 |
Correct |
1 ms |
340 KB |
Output is correct |
46 |
Correct |
1 ms |
340 KB |
Output is correct |
47 |
Correct |
3 ms |
768 KB |
Output is correct |
48 |
Correct |
4 ms |
840 KB |
Output is correct |
49 |
Correct |
3 ms |
792 KB |
Output is correct |
50 |
Correct |
3 ms |
920 KB |
Output is correct |
51 |
Correct |
27 ms |
5084 KB |
Output is correct |
52 |
Correct |
23 ms |
5316 KB |
Output is correct |
53 |
Correct |
29 ms |
7108 KB |
Output is correct |
54 |
Correct |
35 ms |
9504 KB |
Output is correct |
55 |
Correct |
1 ms |
468 KB |
Output is correct |
56 |
Correct |
2 ms |
788 KB |
Output is correct |
57 |
Correct |
1 ms |
468 KB |
Output is correct |
58 |
Correct |
34 ms |
6588 KB |
Output is correct |
59 |
Correct |
32 ms |
6944 KB |
Output is correct |
60 |
Correct |
37 ms |
8340 KB |
Output is correct |
61 |
Correct |
33 ms |
8820 KB |
Output is correct |
62 |
Correct |
65 ms |
13608 KB |
Output is correct |
63 |
Correct |
65 ms |
13868 KB |
Output is correct |
64 |
Correct |
104 ms |
21908 KB |
Output is correct |
65 |
Correct |
362 ms |
68392 KB |
Output is correct |
66 |
Correct |
457 ms |
85260 KB |
Output is correct |
67 |
Correct |
8 ms |
2256 KB |
Output is correct |
68 |
Correct |
5 ms |
1592 KB |
Output is correct |
69 |
Correct |
653 ms |
138484 KB |
Output is correct |
70 |
Correct |
900 ms |
159060 KB |
Output is correct |
71 |
Correct |
1095 ms |
205912 KB |
Output is correct |
72 |
Correct |
979 ms |
184088 KB |
Output is correct |
73 |
Correct |
1074 ms |
194192 KB |
Output is correct |
74 |
Correct |
809 ms |
142164 KB |
Output is correct |
75 |
Correct |
862 ms |
153744 KB |
Output is correct |