Submission #1213044

#TimeUsernameProblemLanguageResultExecution timeMemory
1213044thelegendary08Carnival Tickets (IOI20_tickets)C++17
0 / 100
0 ms328 KiB
#include "tickets.h" #include<bits/stdc++.h> #define pb push_back #define mp make_pair #define f0r(i,n) for(int i = 0; i<n; i++) #define FOR(i, k, n) for(int i = k; i<n; i++) #define vi vector<long long> #define vvi vector<vi> #define pii pair<int,int> #define vb vector<bool> #define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n'; #define dout(x) cout<<x<<' '<<#x<<'\n'; using namespace std; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); /* std::vector<std::vector<int>> answer; for (int i = 0; i < n; i++) { std::vector<int> row(m); for (int j = 0; j < m; j++) { if (j < k) { row[j] = j; } else { row[j] = -1; } } answer.push_back(row); } allocate_tickets(answer); */ vector<vector<int>> ans(n, vector<int>(m, -1)); vi sum(n); f0r(i,n){ sum[i] = accumulate(x[i].begin(), x[i].end(), 0LL); } /* f0r(i,n)f0r(j,m)ans[i][j] = 0; vi v; f0r(i,n)f0r(j,m)v.pb(x[i][j]); sort(v.begin(), v.end()); long long mid = v[n/2]; long long anss = 0; f0r(i, n){ anss += abs(v[i] - mid); } */ vi n1(n, -1); vi n0(n, -1); f0r(i,n){ f0r(j,m){ if(x[i][j] == 1){ n1[i] = j; break; } } } f0r(i,n){ f0r(j,m){ if(x[i][j] == 0){ n0[i] = j; break; } } } long long anss = 0; int zeros = 0; int ones = 0; f0r(i, n){ f0r(j,m){ if(x[i][j] == 0)zeros++; else ones++; } } int r; if(zeros < ones)r = 0; else r = 1; f0r(tt, k){ vi fullr; vb vis(n); f0r(i,n){ if(r == 0){ if(n1[i] == -1){ vis[i] = 1; fullr.pb(i); } } else{ if(n0[i] == -1){ vis[i] = 1; fullr.pb(i); } } } int cur = n/2; for(auto u : fullr){ if(r == 0){ ans[u][n0[u]] = tt; bool ok = 0; for(int i = n0[u] + 1; i < m; i++){ if(x[u][i] == 0){ ok = 1; n0[u] = i; break; } } if(!ok)n0[u] = -1; } else{ ans[u][n1[u]] = tt; bool ok = 0; for(int i = n1[u] + 1; i < m; i++){ if(x[u][i] == 1){ ok = 1; n1[u] = i; break; } } if(!ok)n1[u] = -1; } cur--; anss++; } f0r(i,n){ if(!vis[i]){ if(r == 0){ if(n0[i] == -1 || cur == 0){ ans[i][n1[i]] = tt; bool ok = 0; for(int j = n1[i] + 1; j<m; j++){ if(x[i][j] == 1){ ok = 1; n1[i] = j; break; } } if(!ok)n1[i] = -1; } else{ ans[i][n0[i]] = tt; bool ok = 0; for(int j = n0[i] + 1; j<m; j++){ if(x[i][j] == 0){ ok = 1; n0[i] = j; break; } } if(!ok)n0[i] = -1; cur--; anss++; } } else{ if(n1[i] == -1 || cur == 0){ ans[i][n0[i]] = tt; bool ok = 0; for(int j = n0[i] + 1; j<m; j++){ if(x[i][j] == 0){ ok = 1; n0[i] = j; break; } } if(!ok)n0[i] = -1; } else{ ans[i][n1[i]] = tt; bool ok = 0; for(int j = n1[i] + 1; j<m; j++){ if(x[i][j] == 1){ ok = 1; n1[i] = j; break; } } if(!ok)n1[i] = -1; cur--; anss++; } } } } } allocate_tickets(ans); return anss; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...