| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 286480 | AaronNaidu | 저울 (IOI15_scales) | C++14 | 54 ms | 512 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
int t;
vector<vector<int> > possiblePerms;
bool used[7];
void init(int T) {
t = T;
}
int vectorFind(vector<int> v, int a) {
for (int i = 0; i < v.size(); i++)
{
if (v[i] == a)
{
return i;
}
}
return -1;
}
void generatePerms(vector<int> v) {
if (v.size() == 6)
{
possiblePerms.push_back(v);
return;
}
for (int i = 1; i <= 6; i++)
{
if (!used[i])
{
used[i] = true;
v.push_back(i);
generatePerms(v);
v.pop_back();
used[i] = false;
}
}
}
int checkMin(int a, int b, int c) {
int aCount = 0;
int bCount = 0;
int cCount = 0;
for (auto i : possiblePerms)
{
if (vectorFind(i, a) < vectorFind(i, b) and vectorFind(i, a) < vectorFind(i, c))
{
aCount++;
}
else if (vectorFind(i, b) < vectorFind(i,c))
{
bCount++;
}
else
{
cCount++;
}
}
return max(aCount, max(bCount, cCount));
}
int checkMax(int a, int b, int c) {
int aCount = 0;
int bCount = 0;
int cCount = 0;
for (auto i : possiblePerms)
{
if (vectorFind(i, a) > vectorFind(i, b) and vectorFind(i, a) > vectorFind(i, c))
{
aCount++;
}
else if (vectorFind(i, b) > vectorFind(i,c))
{
bCount++;
}
else
{
cCount++;
}
}
return max(aCount, max(bCount, cCount));
}
int checkMed(int a, int b, int c) {
int aCount = 0;
int bCount = 0;
int cCount = 0;
for (auto i : possiblePerms)
{
if (vectorFind(i, b) < vectorFind(i, a) and vectorFind(i, a) < vectorFind(i, c))
{
aCount++;
}
else if (vectorFind(i, c) < vectorFind(i,a) and vectorFind(i, a) < vectorFind(i, b))
{
aCount++;
}
else if (vectorFind(i, c) < vectorFind(i,b) and vectorFind(i, b) < vectorFind(i, a))
{
bCount++;
}
else if (vectorFind(i, a) < vectorFind(i,b) and vectorFind(i, b) < vectorFind(i, c))
{
bCount++;
}
else
{
cCount++;
}
}
return max(aCount, max(bCount, cCount));
}
int checkOther(int a, int b, int c, int d) {
return 1000000009;
}
void optimalQuestion() {
int minAnswer = 1000000000;
int minType = -1;
int mina, minb, minc, mind;
for (int i = 1; i <= 6; i++)
{
for (int j = i+1; j <= 6; j++)
{
for (int k = j+1; k <= 6; k++)
{
int small = checkMin(i, j, k);
int large = checkMax(i, j, k);
int med = checkMed(i, j, k);
if (small < minAnswer)
{
minAnswer = small;
mina = i;
minb = j;
minc = k;
minType = 1;
}
if (large < minAnswer)
{
minAnswer = large;
mina = i;
minb = j;
minc = k;
minType = 3;
}
if (med < minAnswer)
{
minAnswer = med;
mina = i;
minb = j;
minc = k;
minType = 2;
}
for (int l = k+1; l <= 6; l++)
{
int ans;
ans = checkOther(i, j, k, l);
if (ans < minAnswer)
{
minAnswer = ans;
mina = i;
minb = j;
minc = k;
mind = l;
minType = 4;
}
ans = checkOther(i, j, l, k);
if (ans < minAnswer)
{
minAnswer = ans;
mina = i;
minb = j;
minc = l;
mind = k;
minType = 4;
}
ans = checkOther(i, k, l, j);
if (ans < minAnswer)
{
minAnswer = ans;
mina = i;
minb = k;
minc = l;
mind = j;
minType = 4;
}
ans = checkOther(j, k, l, i);
if (ans < minAnswer)
{
minAnswer = ans;
mina = j;
minb = k;
minc = l;
mind = i;
minType = 4;
}
}
}
}
}
//cout << possiblePerms.size() << " possiblities\n";
if (minType == 1)
{
int x = getLightest(mina, minb, minc);
vector<vector<int> > newPossiblePerms;
for (auto i : possiblePerms)
{
if (vectorFind(i, x) > vectorFind(i, mina))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, minb))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, minc))
{
continue;
}
newPossiblePerms.push_back(i);
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
}
if (minType == 3)
{
int x = getHeaviest(mina, minb, minc);
vector<vector<int> > newPossiblePerms;
for (auto i : possiblePerms)
{
if (vectorFind(i, x) < vectorFind(i, mina))
{
continue;
}
if (vectorFind(i, x) < vectorFind(i, minb))
{
continue;
}
if (vectorFind(i, x) < vectorFind(i, minc))
{
continue;
}
newPossiblePerms.push_back(i);
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
}
if (minType == 2)
{
int x = getMedian(mina, minb, minc);
vector<vector<int> > newPossiblePerms;
for (auto i : possiblePerms)
{
if (vectorFind(i, minb) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, mina))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, mina) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minb))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, minb) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minc))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, minc) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minb))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, mina) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, minc))
{
newPossiblePerms.push_back(i);
}
if (vectorFind(i, minc) > vectorFind(i, x) and vectorFind(i, x) > vectorFind(i, mina))
{
newPossiblePerms.push_back(i);
}
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
}
return;
}
void orderCoins() {
possiblePerms.clear();
generatePerms({});
int x = getLightest(1, 2, 3);
vector<vector<int> > newPossiblePerms;
// cout << possiblePerms.size() << " possiblities\n";
for (auto i : possiblePerms)
{
if (vectorFind(i, x) > vectorFind(i, 1))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, 2))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, 3))
{
continue;
}
newPossiblePerms.push_back(i);
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
// cout << possiblePerms.size() << " possiblities\n";
x = getLightest(4, 5, 6);
for (auto i : possiblePerms)
{
if (vectorFind(i, x) > vectorFind(i, 4))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, 5))
{
continue;
}
if (vectorFind(i, x) > vectorFind(i, 6))
{
continue;
}
newPossiblePerms.push_back(i);
}
possiblePerms = newPossiblePerms;
newPossiblePerms.clear();
while (possiblePerms.size() > 1)
{
optimalQuestion();
}
int finalAnswer[6];
for (int i = 0; i < 6; i++)
{
finalAnswer[i] = possiblePerms[0][i];
}
answer(finalAnswer);
return;
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||