| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 794272 |
2023-07-26T11:48:50 Z |
Josia |
Scales (IOI15_scales) |
C++17 |
|
385 ms |
460 KB |
#include "scales.h"
using namespace std;
#include <bits/stdc++.h>
void init(int T) {
/* ... */
}
int checkComp(vector<vector<int>> perms, vector<int> elems, int op) {
if (op == 0) { // min
vector<vector<vector<int>>> smallPerms(3);
for (int chosen = 0; chosen<3; chosen++) {
for (int i = 0; i < perms.size(); i++) {
if (perms[i][elems[chosen]] < perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] < perms[i][elems[(chosen+2)%3]]) {
smallPerms[chosen].push_back(perms[i]);
}
}
}
set<int> sizes = {(int)smallPerms[0].size(), (int)smallPerms[1].size(), (int)smallPerms[2].size()};
return ((*sizes.rbegin())-(*sizes.begin()));
}
if (op == 1) { // max
vector<vector<vector<int>>> smallPerms(3);
for (int chosen = 0; chosen<3; chosen++) {
for (int i = 0; i < perms.size(); i++) {
if (perms[i][elems[chosen]] > perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] > perms[i][elems[(chosen+2)%3]]) {
smallPerms[chosen].push_back(perms[i]);
}
}
}
set<int> sizes = {(int)smallPerms[0].size(), (int)smallPerms[1].size(), (int)smallPerms[2].size()};
return ((*sizes.rbegin())-(*sizes.begin()));
}
if (op == 2) { // med
vector<vector<vector<int>>> smallPerms(3);
for (int chosen = 0; chosen<3; chosen++) {
for (int i = 0; i < perms.size(); i++) {
if ((perms[i][elems[chosen]] > perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] < perms[i][elems[(chosen+2)%3]]) || (perms[i][elems[chosen]] < perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] > perms[i][elems[(chosen+2)%3]])) {
smallPerms[chosen].push_back(perms[i]);
}
}
}
set<int> sizes = {(int)smallPerms[0].size(), (int)smallPerms[1].size(), (int)smallPerms[2].size()};
return ((*sizes.rbegin())-(*sizes.begin()));
}
if (op == 3) { // weird
// return 1e9;
vector<vector<vector<int>>> smallPerms(3);
for (int chosen = 0; chosen<3; chosen++) {
for (int i = 0; i < perms.size(); i++) {
int comp = perms[i][elems[3]];
set<int> bigger;
for (int j = 0; j<3; j++) if(perms[i][elems[j]]>comp) bigger.insert(perms[i][elems[j]]);
if (bigger.empty()) for (int j = 0; j<3; j++) bigger.insert(perms[i][elems[j]]);
if ((*bigger.begin()) == perms[i][elems[chosen]]) smallPerms[chosen].push_back(perms[i]);
}
}
set<int> sizes = {(int)smallPerms[0].size(), (int)smallPerms[1].size(), (int)smallPerms[2].size()};
return ((*sizes.rbegin())-(*sizes.begin()));
}
}
void updatePerms(vector<vector<int>> &perms, vector<int> elems, int op, int res) {
if (op == 0) { // min
vector<vector<int>> smallPerms;
int chosen = 0;
if (res == elems[1]) chosen = 1;
if (res == elems[2]) chosen = 2;
for (int i = 0; i < perms.size(); i++) {
if (perms[i][elems[chosen]] < perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] < perms[i][elems[(chosen+2)%3]]) {
smallPerms.push_back(perms[i]);
}
}
perms = smallPerms;
}
if (op == 1) { // max
vector<vector<int>> smallPerms;
int chosen = 0;
if (res == elems[1]) chosen = 1;
if (res == elems[2]) chosen = 2;
for (int i = 0; i < perms.size(); i++) {
if (perms[i][elems[chosen]] > perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] > perms[i][elems[(chosen+2)%3]]) {
smallPerms.push_back(perms[i]);
}
}
perms = smallPerms;
}
if (op == 2) { // med
vector<vector<int>> smallPerms;
int chosen = 0;
if (res == elems[1]) chosen = 1;
if (res == elems[2]) chosen = 2;
for (int i = 0; i < perms.size(); i++) {
if ((perms[i][elems[chosen]] > perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] < perms[i][elems[(chosen+2)%3]]) || (perms[i][elems[chosen]] < perms[i][elems[(chosen+1)%3]] && perms[i][elems[chosen]] > perms[i][elems[(chosen+2)%3]])) {
smallPerms.push_back(perms[i]);
}
}
perms = smallPerms;
}
if (op == 3) { // weird
vector<vector<int>> smallPerms;
int chosen = 0;
if (res == elems[1]) chosen = 1;
if (res == elems[2]) chosen = 2;
for (int i = 0; i < perms.size(); i++) {
int comp = perms[i][elems[3]];
set<int> bigger;
for (int j = 0; j<3; j++) if(perms[i][elems[j]]>comp) bigger.insert(perms[i][elems[j]]);
if (bigger.empty()) for (int j = 0; j<3; j++) bigger.insert(perms[i][elems[j]]);
if ((*bigger.begin()) == perms[i][elems[chosen]]) smallPerms.push_back(perms[i]);
}
perms = smallPerms;
}
}
void orderCoins() {
vector<vector<int>> perms;
vector<int> currPerm = {0,1,2,3,4,5};
do {
perms.push_back(currPerm);
} while(next_permutation(currPerm.begin(), currPerm.end()));
auto rng = std::default_random_engine {4};
while (perms.size() > 1) {
// cerr << perms.size() << "\n";
int best = 1e9;
vector<int> elems;
int OP = -1;
vector<int> I = {0,1,2,3,4,5}; shuffle(I.begin(), I.end(), rng);
for (int i:I) {
vector<int> J = {0,1,2,3,4,5}; shuffle(J.begin(), J.end(), rng);
for (int j:J) {
vector<int> K = {0,1,2,3,4,5}; shuffle(K.begin(), K.end(), rng);
for (int k:K) {
if (i == j || j == k || i == k) continue;
vector<int> Op = {0,1,2}; shuffle(Op.begin(), Op.end(), rng);
for (int op:Op) {
if (checkComp(perms, {i,j,k}, op) < best) {elems = {i,j,k}; OP = op; best = checkComp(perms, {i,j,k}, op);}
}
vector<int> L = {0,1,2,3,4,5}; shuffle(L.begin(), L.end(), rng);
for (int l:L) {
if (i == j || j == k || i == k || l == i || l == j || l == k) continue;
if (checkComp(perms, {i,j,k,l}, 3) < best) {elems = {i,j,k,l}; OP = 3; best = checkComp(perms, {i,j,k,l}, 3);}
}
if (best < 1) break;
}
if (best < 1) break;
}
if (best < 1) break;
}
assert(OP != -1);
// cerr << OP << "\n";
if (OP==0) updatePerms(perms, elems, OP, getLightest(elems[0]+1, elems[1]+1, elems[2]+1)-1);
if (OP==1) updatePerms(perms, elems, OP, getHeaviest(elems[0]+1, elems[1]+1, elems[2]+1)-1);
if (OP==2) updatePerms(perms, elems, OP, getMedian(elems[0]+1, elems[1]+1, elems[2]+1)-1);
if (OP==3) updatePerms(perms, elems, OP, getNextLightest(elems[0]+1, elems[1]+1, elems[2]+1, elems[3]+1)-1);
}
// cerr << perms.size() << "\n";
int res[6];
for (int i = 0; i<6; i++) {
res[perms[0][i]] = i+1;
}
answer(res);
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:6:15: warning: unused parameter 'T' [-Wunused-parameter]
6 | void init(int T) {
| ~~~~^
scales.cpp: In function 'int checkComp(std::vector<std::vector<int> >, std::vector<int>, int)':
scales.cpp:16:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for (int i = 0; i < perms.size(); i++) {
| ~~^~~~~~~~~~~~~~
scales.cpp:31:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int i = 0; i < perms.size(); i++) {
| ~~^~~~~~~~~~~~~~
scales.cpp:46:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for (int i = 0; i < perms.size(); i++) {
| ~~^~~~~~~~~~~~~~
scales.cpp:62:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i = 0; i < perms.size(); i++) {
| ~~^~~~~~~~~~~~~~
scales.cpp: In function 'void updatePerms(std::vector<std::vector<int> >&, std::vector<int>, int, int)':
scales.cpp:85:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i < perms.size(); i++) {
| ~~^~~~~~~~~~~~~~
scales.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for (int i = 0; i < perms.size(); i++) {
| ~~^~~~~~~~~~~~~~
scales.cpp:111:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | for (int i = 0; i < perms.size(); i++) {
| ~~^~~~~~~~~~~~~~
scales.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
124 | for (int i = 0; i < perms.size(); i++) {
| ~~^~~~~~~~~~~~~~
scales.cpp: In function 'int checkComp(std::vector<std::vector<int> >, std::vector<int>, int)':
scales.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
76 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
340 ms |
340 KB |
Output is correct |
| 2 |
Correct |
359 ms |
412 KB |
Output is correct |
| 3 |
Correct |
341 ms |
412 KB |
Output is correct |
| 4 |
Partially correct |
338 ms |
408 KB |
Output is partially correct |
| 5 |
Correct |
369 ms |
424 KB |
Output is correct |
| 6 |
Partially correct |
334 ms |
424 KB |
Output is partially correct |
| 7 |
Partially correct |
342 ms |
420 KB |
Output is partially correct |
| 8 |
Partially correct |
348 ms |
424 KB |
Output is partially correct |
| 9 |
Partially correct |
338 ms |
428 KB |
Output is partially correct |
| 10 |
Partially correct |
385 ms |
420 KB |
Output is partially correct |
| 11 |
Partially correct |
342 ms |
420 KB |
Output is partially correct |
| 12 |
Correct |
342 ms |
420 KB |
Output is correct |
| 13 |
Correct |
336 ms |
424 KB |
Output is correct |
| 14 |
Correct |
337 ms |
416 KB |
Output is correct |
| 15 |
Correct |
331 ms |
412 KB |
Output is correct |
| 16 |
Partially correct |
346 ms |
424 KB |
Output is partially correct |
| 17 |
Partially correct |
370 ms |
432 KB |
Output is partially correct |
| 18 |
Correct |
340 ms |
424 KB |
Output is correct |
| 19 |
Partially correct |
332 ms |
416 KB |
Output is partially correct |
| 20 |
Partially correct |
339 ms |
412 KB |
Output is partially correct |
| 21 |
Correct |
362 ms |
412 KB |
Output is correct |
| 22 |
Partially correct |
337 ms |
408 KB |
Output is partially correct |
| 23 |
Partially correct |
340 ms |
428 KB |
Output is partially correct |
| 24 |
Partially correct |
342 ms |
428 KB |
Output is partially correct |
| 25 |
Partially correct |
354 ms |
412 KB |
Output is partially correct |
| 26 |
Partially correct |
333 ms |
412 KB |
Output is partially correct |
| 27 |
Partially correct |
341 ms |
412 KB |
Output is partially correct |
| 28 |
Partially correct |
353 ms |
412 KB |
Output is partially correct |
| 29 |
Partially correct |
342 ms |
460 KB |
Output is partially correct |
| 30 |
Partially correct |
364 ms |
424 KB |
Output is partially correct |
| 31 |
Partially correct |
346 ms |
420 KB |
Output is partially correct |
| 32 |
Correct |
341 ms |
404 KB |
Output is correct |
| 33 |
Correct |
333 ms |
424 KB |
Output is correct |
| 34 |
Correct |
342 ms |
424 KB |
Output is correct |
| 35 |
Correct |
368 ms |
416 KB |
Output is correct |
| 36 |
Partially correct |
340 ms |
424 KB |
Output is partially correct |
| 37 |
Partially correct |
338 ms |
416 KB |
Output is partially correct |
| 38 |
Partially correct |
335 ms |
428 KB |
Output is partially correct |
| 39 |
Partially correct |
335 ms |
424 KB |
Output is partially correct |
| 40 |
Partially correct |
356 ms |
412 KB |
Output is partially correct |
