| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 713727 | lam | 저울 (IOI15_scales) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "scales.h"
using namespace std;
vector <vector <int>> asks, pos, perm;
int lt3[11];
int query(vector <int> v)
{
if (v[0] == 0) return getLightest(v[1],v[2],v[3]);
if (v[0] == -1) return getMedian(v[1],v[2],v[3]);
if (v[0] == -2) return getHeaviest(v[1],v[2],v[3]);
return getNextLightest(v[1],v[2],v[3],v[0]);
}
int query2(int id, vector <int> v)
{
sort(v.begin()+1,v.end(),[&](int a, int b){
return pos[id][a] < pos[id][b]; });
if (v[0] == 0) return v[1];
if (v[0] == -1) return v[2];
if (v[0] == -2) return v[3];
for (int i=1; i<=3; i++) if (pos[id][i] > pos[id][0]) return v[i];
return v[1];
}
struct Cmp {
bool operator() (const bitset<720> &a, const bitset<720> &b) const {
for (int i=0; i<720; i++) if (a[i] != b[i]) return a[i] < b[i];
return false;
}
};
map<bitset<720>,vector <int>,Cmp> mp[10];
bool check(bitset<720> bs, int level)
{
if (bs.count()<=1) return 1;
if (mp[level].count(bs)) return !mp[level][bs].empty();
for (vector <int> v:asks)
{
vector <int> id(7);
for (int i=1; i<=3; i++) id[v[i]] = i-1;
vector<bitset<720>> nxt(3);
for (int i=0; i<720; i++) if (bs[i]) nxt[id[query2(i,v)]][i] = 1;
bool ccheck = 1;
for (auto bs2:nxt)
if (bs2.count() > lt3[level-1])
{
ccheck = 0;
break;
}
if (!ccheck) continue;
for (auto bs2:nxt)
if (!check(bs2,level-1))
{
ccheck = 0;
break;
}
if (ccheck)
{
mp[level][bs] = v;
return 1;
}
}
mp[level][bs] = {};
return 0;
}
void Init(int test)
{
lt3[0] = 1;
for (int i=1; i<=10; i++) lt3[i] = lt3[i-1] * 3;
vector <int> v;
for (int i=1; i<=6; i++) v.push_back(i);
do
{
vector <int> id(7);
for (int i=0; i<6; i++) id[v[i]] = i+1;
pos.push_back(id);
perm.push_back(v);
}
while (next_permutation(v.begin(),v.end()));
for (int a=1; a<=6; a++)
for (int b=a+1; b<=6; b++)
for (int c=b+1; c<=6; c++)
{
for (int d=1; d<=6; d++) if (d!=a&&d!=b&&d!=c) asks.push_back({d,a,b,c});
for (int i=-2; i<=0; i++) asks.push_back({i,a,b,c});
}
bitset<720> bs;
for (int i=0; i<720; i++) bs[i] = 1;
bool temp = check(bs,6);
}
void orderCoins()
{
bitset<720> bs;
for (int i=0; i<720; i++) bs[i] = 1;
for (int i=6; i>=1; i--)
{
vector <int> v = mp[i][bs];
int temp = query(v);
for (int j=0; j<720; j++) if (bs[j]&&query2(j,v)!=temp) bs[j] = 0;
}
int res[6];
int it = -1;
for (int i=0; i<720; i++) if (bs[i]) it = i;
for (int i=0; i<6; i++) res[i] = perm[it][i];
answer(res);
}