/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "tickets.h"
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
ll Value(vector<vector<ll> > ans, vector<vector<int> > X)
{
ll val=0LL;
REP(i,0,X.size()) {REP(j,0,X[i].size()) {val+=((ll) (ans[i][j]*X[i][j]));}}
return val;
}
vector<vector<int> > Order(vector<vector<ll> > ans, ll K)
{
ll N = ans.size(); ll M = ans[0].size();
vector<vector<int> > a; vector<int> xx; VV(xx,M,-1); VV(a,N,xx);
vector<pl> ones; REP(i,0,N) {ll cursum=0; REP(j,0,M) {cursum+=ans[i][j];} ones.pb({cursum,i});}
sort(whole(ones));
vector<ll> indleft,indright; VV(indleft,N,0); VV(indright,N,M-1); ll ind;
REP(i,0,K)
{
vector<pl> newones;
REP(j,0,N/2) {ind = ones[j].ss; newones.pb({ones[j].ff+1,ind}); a[ind][indleft[ind]]=i; indleft[ind]++;}
REP(j,N/2,N) {ind = ones[j].ss; newones.pb({ones[j].ff-1,ind}); a[ind][indright[ind]]=i; indright[ind]--;}
sort(whole(newones)); ones=newones;
}
return a;
}
ll find_maximum(int k, vector<vector<int> > x)
{
ll N = x.size(); ll M = x[0].size(); ll K = (ll) k;
vector<vector<ll> > ans; vector<ll> xx; VV(xx,M,0); VV(ans,N,xx);
if(M==K)
{
vector<pair<ll,pl> > vals; REP(i,0,N) {REP(j,0,M) {vals.pb({x[i][j],{i,j}});}}
sort(whole(vals)); REP(i,0,(N*M)/2) {ans[vals[i].ss.ff][vals[i].ss.ss]=-1;} REP(i,(N*M)/2,N*M) {ans[vals[i].ss.ff][vals[i].ss.ss]=1;}
}
else
{
set<pl> small,big; vector<ll> ind; VV(ind,N/2,0); VV(ind,N/2,K); set<pl>::iterator it;
REP(i,0,N)
{
ll val_small; if(ind[i]==0) {val_small=-INF;} else {val_small=x[i][ind[i]-1]+x[i][ind[i]+M-K-1];}
ll val_big; if(ind[i]==K) {val_big=INF;} else {val_big=x[i][ind[i]]+x[i][ind[i]+M-K];}
small.insert({val_small,i}); big.insert({val_big,i});
}
while(1>0)
{
it=small.end(); it--; pl max_small = *it; small.erase(it);
it=big.begin(); pl min_big = *it; big.erase(it);
if(max_small.ff<=min_big.ff) {break;}
ll ind_small = max_small.ss; ll ind_big = min_big.ss;
ind[ind_small]--; ind[ind_big]++;
ll val_small,val_big;
ll i=ind_small;
if(ind[i]==0) {val_small=-INF;} else {val_small=x[i][ind[i]-1]+x[i][ind[i]+M-K-1];}
if(ind[i]==K) {val_big=INF;} else {val_big=x[i][ind[i]]+x[i][ind[i]+M-K];}
small.insert({val_small,i}); big.insert({val_big,i});
i=ind_big;
if(ind[i]==0) {val_small=-INF;} else {val_small=x[i][ind[i]-1]+x[i][ind[i]+M-K-1];}
if(ind[i]==K) {val_big=INF;} else {val_big=x[i][ind[i]]+x[i][ind[i]+M-K];}
small.insert({val_small,i}); big.insert({val_big,i});
}
REP(i,0,N) {REP(j,0,ind[i]) {ans[i][j]=-1;} REP(j,ind[i]+M-K,M) {ans[i][j]=1;}}
}
allocate_tickets(Order(ans,K));
return Value(ans,x);
}
Compilation message
tickets.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
5 | #pragma GCC optimization ("O3")
|
tickets.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
6 | #pragma GCC optimization ("unroll-loops")
|
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
596 KB |
Output is correct |
5 |
Correct |
20 ms |
4300 KB |
Output is correct |
6 |
Correct |
509 ms |
78296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
296 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
19 ms |
3604 KB |
Output is correct |
6 |
Correct |
489 ms |
83192 KB |
Output is correct |
7 |
Correct |
520 ms |
83660 KB |
Output is correct |
8 |
Correct |
4 ms |
916 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
300 KB |
Output is correct |
12 |
Correct |
6 ms |
1108 KB |
Output is correct |
13 |
Correct |
18 ms |
3064 KB |
Output is correct |
14 |
Correct |
19 ms |
3092 KB |
Output is correct |
15 |
Correct |
585 ms |
84204 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 |
3 ms |
664 KB |
Output is correct |
5 |
Correct |
30 ms |
4940 KB |
Output is correct |
6 |
Correct |
5 ms |
1044 KB |
Output is correct |
7 |
Correct |
7 ms |
1172 KB |
Output is correct |
8 |
Correct |
829 ms |
134360 KB |
Output is correct |
9 |
Correct |
796 ms |
132040 KB |
Output is correct |
10 |
Correct |
837 ms |
152404 KB |
Output is correct |
11 |
Correct |
851 ms |
156128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
572 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 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 |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
3 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
572 KB |
Output is correct |
3 |
Correct |
3 ms |
596 KB |
Output is correct |
4 |
Correct |
3 ms |
596 KB |
Output is correct |
5 |
Correct |
3 ms |
596 KB |
Output is correct |
6 |
Correct |
3 ms |
596 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 |
468 KB |
Output is correct |
10 |
Correct |
3 ms |
596 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
3 ms |
596 KB |
Output is correct |
13 |
Correct |
22 ms |
4292 KB |
Output is correct |
14 |
Correct |
30 ms |
4252 KB |
Output is correct |
15 |
Correct |
31 ms |
4280 KB |
Output is correct |
16 |
Correct |
31 ms |
5808 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
3 ms |
596 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
31 ms |
4076 KB |
Output is correct |
21 |
Correct |
34 ms |
4640 KB |
Output is correct |
22 |
Correct |
38 ms |
4688 KB |
Output is correct |
23 |
Correct |
39 ms |
5148 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
724 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
20 ms |
4300 KB |
Output is correct |
12 |
Correct |
509 ms |
78296 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
1 ms |
296 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
19 ms |
3604 KB |
Output is correct |
18 |
Correct |
489 ms |
83192 KB |
Output is correct |
19 |
Correct |
520 ms |
83660 KB |
Output is correct |
20 |
Correct |
4 ms |
916 KB |
Output is correct |
21 |
Correct |
1 ms |
304 KB |
Output is correct |
22 |
Correct |
0 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
300 KB |
Output is correct |
24 |
Correct |
6 ms |
1108 KB |
Output is correct |
25 |
Correct |
18 ms |
3064 KB |
Output is correct |
26 |
Correct |
19 ms |
3092 KB |
Output is correct |
27 |
Correct |
585 ms |
84204 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
3 ms |
664 KB |
Output is correct |
32 |
Correct |
30 ms |
4940 KB |
Output is correct |
33 |
Correct |
5 ms |
1044 KB |
Output is correct |
34 |
Correct |
7 ms |
1172 KB |
Output is correct |
35 |
Correct |
829 ms |
134360 KB |
Output is correct |
36 |
Correct |
796 ms |
132040 KB |
Output is correct |
37 |
Correct |
837 ms |
152404 KB |
Output is correct |
38 |
Correct |
851 ms |
156128 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
2 ms |
572 KB |
Output is correct |
41 |
Correct |
3 ms |
596 KB |
Output is correct |
42 |
Correct |
3 ms |
596 KB |
Output is correct |
43 |
Correct |
3 ms |
596 KB |
Output is correct |
44 |
Correct |
3 ms |
596 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 |
468 KB |
Output is correct |
48 |
Correct |
3 ms |
596 KB |
Output is correct |
49 |
Correct |
4 ms |
596 KB |
Output is correct |
50 |
Correct |
3 ms |
596 KB |
Output is correct |
51 |
Correct |
22 ms |
4292 KB |
Output is correct |
52 |
Correct |
30 ms |
4252 KB |
Output is correct |
53 |
Correct |
31 ms |
4280 KB |
Output is correct |
54 |
Correct |
31 ms |
5808 KB |
Output is correct |
55 |
Correct |
1 ms |
340 KB |
Output is correct |
56 |
Correct |
3 ms |
596 KB |
Output is correct |
57 |
Correct |
1 ms |
468 KB |
Output is correct |
58 |
Correct |
31 ms |
4076 KB |
Output is correct |
59 |
Correct |
34 ms |
4640 KB |
Output is correct |
60 |
Correct |
38 ms |
4688 KB |
Output is correct |
61 |
Correct |
39 ms |
5148 KB |
Output is correct |
62 |
Correct |
57 ms |
11376 KB |
Output is correct |
63 |
Correct |
73 ms |
11332 KB |
Output is correct |
64 |
Correct |
88 ms |
12936 KB |
Output is correct |
65 |
Correct |
417 ms |
44876 KB |
Output is correct |
66 |
Correct |
383 ms |
50500 KB |
Output is correct |
67 |
Correct |
6 ms |
1300 KB |
Output is correct |
68 |
Correct |
5 ms |
1172 KB |
Output is correct |
69 |
Correct |
505 ms |
99672 KB |
Output is correct |
70 |
Correct |
924 ms |
100748 KB |
Output is correct |
71 |
Correct |
943 ms |
156048 KB |
Output is correct |
72 |
Correct |
843 ms |
86336 KB |
Output is correct |
73 |
Correct |
1224 ms |
127796 KB |
Output is correct |
74 |
Correct |
670 ms |
84716 KB |
Output is correct |
75 |
Correct |
886 ms |
100408 KB |
Output is correct |