#include "tickets.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fi first
#define se second
#define ld long double
#define pb push_back
vector<std::vector<signed>> ans;
bool vis[2000][2000];
int presi[2000];
int N,M;
vector<int> x[2000],y[2000];
vector<int> start(2001);
long long find_maximum(signed k, std::vector<std::vector<signed>> z) {
N = z.size();
M = z[0].size();
vector<tuple<int,int,int> >v;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
v.pb({z[i][j],i,j});
}
}
sort(v.begin(),v.end());
vector<pair<int,int> > ma,mi;
int tot=0;
for(int i=0;i<v.size();i++){
auto [a,b,c]=v[i];
if(presi[b]==k)continue;
if(vis[b][c])continue;
presi[b]++;
vis[b][c]=1;
mi.pb({b,c});
tot-=a;
if(mi.size()==N/2*k)break;
}
for(int i=v.size()-1;i>=0;i--){
auto [a,b,c]=v[i];
if(presi[b]==k)continue;
if(vis[b][c])continue;
presi[b]++;
vis[b][c]=1;
ma.pb({b,c});
tot+=a;
if(ma.size()==N/2*k)break;
}
for (int i=0;i<N;i++) {
vector<signed> row(M,-1);
ans.pb(row);
}
for(auto [a,b]:mi)x[a].pb(b);
for(auto [a,b]:ma)y[a].pb(b);
int pos=0;
for(int i=0;i<N;i++){
start[i]=pos;
for(int j=0;j<x[i].size();j++){
ans[i][x[i][j]]=pos;
pos=(pos+1)%k;
}
}
for(int i=0;i<N;i++){
pos=(start[i]-1+k)%k;
for(int j=0;j<y[i].size();j++){
ans[i][y[i][j]]=pos;
pos=(pos-1+k)%k;
}
}
allocate_tickets(ans);
return tot;
}
Compilation message
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:30:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::tuple<long long int, long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
tickets.cpp:38:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
38 | if(mi.size()==N/2*k)break;
| ~~~~~~~~~^~~~~~~
tickets.cpp:48:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
48 | if(ma.size()==N/2*k)break;
| ~~~~~~~~~^~~~~~~
tickets.cpp:63:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int j=0;j<x[i].size();j++){
| ~^~~~~~~~~~~~
tickets.cpp:70:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for(int j=0;j<y[i].size();j++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
1100 KB |
Output is correct |
6 |
Correct |
5 ms |
3788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
1 ms |
332 KB |
Contestant returned 2307346107 while correct return value is 2727881086. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
388 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Incorrect |
1 ms |
412 KB |
Contestant returned 23 while correct return value is 25. |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
388 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
5 ms |
1124 KB |
Output is correct |
5 |
Correct |
44 ms |
8528 KB |
Output is correct |
6 |
Correct |
7 ms |
1568 KB |
Output is correct |
7 |
Correct |
11 ms |
4808 KB |
Output is correct |
8 |
Correct |
1196 ms |
165116 KB |
Output is correct |
9 |
Correct |
1124 ms |
156032 KB |
Output is correct |
10 |
Correct |
1083 ms |
154284 KB |
Output is correct |
11 |
Correct |
1113 ms |
165204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
3 ms |
908 KB |
Contestant returned 39141745836 while correct return value is 39376297182. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Incorrect |
3 ms |
908 KB |
Contestant returned 39141745836 while correct return value is 39376297182. |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
588 KB |
Output is correct |
5 |
Correct |
1 ms |
1100 KB |
Output is correct |
6 |
Correct |
5 ms |
3788 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Incorrect |
1 ms |
332 KB |
Contestant returned 2307346107 while correct return value is 2727881086. |
9 |
Halted |
0 ms |
0 KB |
- |