| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 158382 |
2019-10-16T20:49:01 Z |
johutha |
Scales (IOI15_scales) |
C++14 |
|
775 ms |
584 KB |
#include "scales.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
enum optype
{
Lightest, Median, Heaviest, Next,
};
void init(int t)
{
}
bool works(string input, optype op, int res, int a, int b, int c, int d = -1)
{
vector<int> srtd;
int dpos = -1;
for (int i = 0; i < 6; i++)
{
int nm = input[i] - '0';
if (nm == d) dpos = srtd.size();
if (nm == a || nm == b || nm == c || nm == d) srtd.push_back(nm);
}
if (op == Lightest) return srtd[0] == res;
if (op == Median) return srtd[1] == res;
if (op == Heaviest) return srtd[2] == res;
return srtd[(dpos + 1) % 4] == res;
}
void orderCoins()
{
vector<string> allst;
string st = "123456";
do
{
allst.push_back(st);
} while (next_permutation(st.begin(), st.end()));
while (allst.size() > 1)
{
vector<int> lbst;
int lbv = 1000;
for (int i1 = 1; i1 < 7; i1++)
{
for (int i2 = 1; i2 < i1; i2++)
{
for (int i3 = 1; i3 < i2; i3++)
{
int s1 = 0;
int s2 = 0;
int s3 = 0;
for (string s : allst)
{
if (works(s, Lightest, i1, i1, i2, i3)) s1++;
else if (works(s, Lightest, i2, i1, i2, i3)) s2++;
else s3++;
}
if (max(s1, max(s2, s3)) < lbv)
{
lbv = max(s1, max(s2, s3));
lbst = {i1, i2, i3};
}
}
}
}
vector<int> mbst;
int mbv = 1000;
for (int i1 = 1; i1 < 7; i1++)
{
for (int i2 = 1; i2 < i1; i2++)
{
for (int i3 = 1; i3 < i2; i3++)
{
int s1 = 0;
int s2 = 0;
int s3 = 0;
for (string s : allst)
{
if (works(s, Median, i1, i1, i2, i3)) s1++;
else if (works(s, Median, i2, i1, i2, i3)) s2++;
else s3++;
}
if (max(s1, max(s2, s3)) < mbv)
{
mbv = max(s1, max(s2, s3));
mbst = {i1, i2, i3};
}
}
}
}
vector<int> hbst;
int hbv = 1000;
for (int i1 = 1; i1 < 7; i1++)
{
for (int i2 = 1; i2 < i1; i2++)
{
for (int i3 = 1; i3 < i2; i3++)
{
int s1 = 0;
int s2 = 0;
int s3 = 0;
for (string s : allst)
{
if (works(s, Heaviest, i1, i1, i2, i3)) s1++;
else if (works(s, Heaviest, i2, i1, i2, i3)) s2++;
else s3++;
}
if (max(s1, max(s2, s3)) < hbv)
{
hbv = max(s1, max(s2, s3));
hbst = {i1, i2, i3};
}
}
}
}
vector<int> nbst;
int nbv = 1000;
for (int i1 = 1; i1 < 7; i1++)
{
for (int i2 = 1; i2 < i1; i2++)
{
for (int i3 = 1; i3 < i2; i3++)
{
for (int i4 = 1; i4 < 7; i4++)
{
if (i4 == i1 || i4 == i2 || i4 == i3) continue;
int s1 = 0;
int s2 = 0;
int s3 = 0;
for (string s : allst)
{
if (works(s, Next, i1, i1, i2, i3, i4)) s1++;
else if (works(s, Next, i2, i1, i2, i3, i4)) s2++;
else s3++;
}
if (max(s1, max(s2, s3)) < nbv)
{
nbv = max(s1, max(s2, s3));
nbst = {i1, i2, i3, i4};
}
}
}
}
}
vector<string> nbt;
if (lbv < mbv && lbv < hbv && lbv < nbv)
{
int r = getLightest(lbst[0], lbst[1], lbst[2]);
for (string s : allst)
{
if (works(s, Lightest, r, lbst[0], lbst[1], lbst[2])) nbt.push_back(s);
}
}
else if (mbv < hbv && mbv < nbv)
{
int r = getMedian(mbst[0], mbst[1], mbst[2]);
for (string s : allst)
{
if (works(s, Median, r, mbst[0], mbst[1], mbst[2])) nbt.push_back(s);
}
}
else if (hbv < nbv)
{
int r = getHeaviest(hbst[0], hbst[1], hbst[2]);
for (string s : allst)
{
if (works(s, Heaviest, r, hbst[0], hbst[1], hbst[2])) nbt.push_back(s);
}
}
else
{
int r = getNextLightest(nbst[0], nbst[1], nbst[2], nbst[3]);
for (string s : allst)
{
if (works(s, Next, r, nbst[0], nbst[1], nbst[2], nbst[3])) nbt.push_back(s);
}
}
allst = nbt;
}
vector<int> res;
for (int i = 0; i < 6; i++)
{
res.push_back(allst[0][i] - '0');
}
answer(res.data());
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:13:15: warning: unused parameter 't' [-Wunused-parameter]
void init(int t)
^
scales.cpp: In function 'bool works(std::__cxx11::string, optype, int, int, int, int, int)':
scales.cpp:25:38: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
if (nm == d) dpos = srtd.size();
~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
755 ms |
376 KB |
Output is partially correct |
| 2 |
Partially correct |
734 ms |
376 KB |
Output is partially correct |
| 3 |
Partially correct |
726 ms |
420 KB |
Output is partially correct |
| 4 |
Partially correct |
748 ms |
416 KB |
Output is partially correct |
| 5 |
Partially correct |
729 ms |
420 KB |
Output is partially correct |
| 6 |
Partially correct |
726 ms |
420 KB |
Output is partially correct |
| 7 |
Partially correct |
733 ms |
424 KB |
Output is partially correct |
| 8 |
Partially correct |
726 ms |
376 KB |
Output is partially correct |
| 9 |
Partially correct |
729 ms |
416 KB |
Output is partially correct |
| 10 |
Partially correct |
727 ms |
504 KB |
Output is partially correct |
| 11 |
Partially correct |
728 ms |
504 KB |
Output is partially correct |
| 12 |
Partially correct |
775 ms |
504 KB |
Output is partially correct |
| 13 |
Partially correct |
733 ms |
476 KB |
Output is partially correct |
| 14 |
Partially correct |
728 ms |
504 KB |
Output is partially correct |
| 15 |
Partially correct |
728 ms |
500 KB |
Output is partially correct |
| 16 |
Partially correct |
729 ms |
380 KB |
Output is partially correct |
| 17 |
Partially correct |
728 ms |
416 KB |
Output is partially correct |
| 18 |
Partially correct |
730 ms |
416 KB |
Output is partially correct |
| 19 |
Partially correct |
727 ms |
584 KB |
Output is partially correct |
| 20 |
Partially correct |
728 ms |
504 KB |
Output is partially correct |
| 21 |
Partially correct |
743 ms |
504 KB |
Output is partially correct |
| 22 |
Partially correct |
735 ms |
416 KB |
Output is partially correct |
| 23 |
Partially correct |
756 ms |
420 KB |
Output is partially correct |
| 24 |
Correct |
725 ms |
376 KB |
Output is correct |
| 25 |
Partially correct |
728 ms |
504 KB |
Output is partially correct |
| 26 |
Partially correct |
753 ms |
504 KB |
Output is partially correct |
| 27 |
Partially correct |
727 ms |
416 KB |
Output is partially correct |
| 28 |
Partially correct |
743 ms |
424 KB |
Output is partially correct |
| 29 |
Partially correct |
726 ms |
416 KB |
Output is partially correct |
| 30 |
Correct |
734 ms |
476 KB |
Output is correct |
| 31 |
Partially correct |
730 ms |
420 KB |
Output is partially correct |
| 32 |
Partially correct |
729 ms |
476 KB |
Output is partially correct |
| 33 |
Partially correct |
729 ms |
476 KB |
Output is partially correct |
| 34 |
Partially correct |
734 ms |
504 KB |
Output is partially correct |
| 35 |
Partially correct |
728 ms |
504 KB |
Output is partially correct |
| 36 |
Partially correct |
727 ms |
416 KB |
Output is partially correct |
| 37 |
Partially correct |
737 ms |
504 KB |
Output is partially correct |
| 38 |
Partially correct |
732 ms |
480 KB |
Output is partially correct |
| 39 |
Partially correct |
736 ms |
416 KB |
Output is partially correct |
| 40 |
Partially correct |
727 ms |
412 KB |
Output is partially correct |
