# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
584840 | hibiki | 저울 (IOI15_scales) | C++11 | 84 ms | 460 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
struct query
{
int a,b,c,d,type;
query() {};
query(int a, int b, int c, int d, int type): a(a), b(b), c(c), d(d), type(type) {};
};
vector<vector<int> > all;
vector<query> ask;
int fi_median(int a,int b,int c)
{
if(max({a, b, c}) != a && min({a, b, c}) != a) return a;
if(max({a, b, c}) != b && min({a, b, c}) != b) return b;
if(max({a, b, c}) != c && min({a, b, c}) != c) return c;
exit(-1);
return -1;
}
int fi_next_light(int a,int b,int c,int d)
{
int ret = 1e9;
if(a > d)
ret = min(ret, a);
if(b > d)
ret = min(ret, b);
if(c > d)
ret = min(ret, c);
if(ret == 1e9)
ret = min({a, b, c});
return ret;
}
void init(int T) {
vector<int> v;
for(int i = 0; i < 6; i++) v.pb(i);
do {
all.pb(v);
} while(next_permutation(all(v)));
for(int a = 0; a < 6; a++)
for(int b = a + 1; b < 6; b++)
for(int c = b + 1; c < 6; c++)
{
ask.pb(query(a, b, c, 0, 0));
ask.pb(query(a, b, c, 0, 1));
ask.pb(query(a, b, c, 0, 2));
for(int d = 0; d < 6; d++)
{
if(a == d || b == d || c == d) continue;
ask.pb({a, b, c, d, 3});
}
}
}
void orderCoins() {
vector<vector<int> > pos = all;
while(1)
{
if(sz(pos) == 1)
{
int ans[6];
for(int i = 0; i < 6; i++)
ans[(*pos.begin())[i]] = i + 1;
answer(ans);
return ;
}
vector<query> vbest;
int val = 1e9;
for(auto cask: ask)
{
if(cask.type == 0)
{
int ta = 0, tb = 0, tc = 0;
for(auto nw: pos)
{
if(max({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.a]) ta++;
if(max({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.b]) tb++;
if(max({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.c]) tc++;
}
int mx = max({ta, tb, tc});
if(mx < val)
{
val = mx;
vbest.clear();
vbest.pb(cask);
}
else if(mx == val)
{
vbest.pb(cask);
}
}
else if(cask.type == 1)
{
int ta = 0, tb = 0, tc = 0;
for(auto nw: pos)
{
if(min({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.a]) ta++;
if(min({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.b]) tb++;
if(min({nw[cask.a], nw[cask.b], nw[cask.c]}) == nw[cask.c]) tc++;
}
int mx = max({ta, tb, tc});
if(mx < val)
{
val = mx;
vbest.clear();
vbest.pb(cask);
}
else if(mx == val)
{
vbest.pb(cask);
}
}
else if(cask.type == 2)
{
int ta = 0, tb = 0, tc = 0;
for(auto nw: pos)
{
if(fi_median(nw[cask.a], nw[cask.b], nw[cask.c]) == nw[cask.a]) ta++;
if(fi_median(nw[cask.a], nw[cask.b], nw[cask.c]) == nw[cask.b]) tb++;
if(fi_median(nw[cask.a], nw[cask.b], nw[cask.c]) == nw[cask.c]) tc++;
}
int mx = max({ta, tb, tc});
if(mx < val)
{
val = mx;
vbest.clear();
vbest.pb(cask);
}
else if(mx == val)
{
vbest.pb(cask);
}
}
else
{
int ta = 0, tb = 0, tc = 0;
for(auto nw: pos)
{
if(fi_next_light(nw[cask.a], nw[cask.b], nw[cask.c], nw[cask.d]) == nw[cask.a]) ta++;
if(fi_next_light(nw[cask.a], nw[cask.b], nw[cask.c], nw[cask.d]) == nw[cask.b]) tb++;
if(fi_next_light(nw[cask.a], nw[cask.b], nw[cask.c], nw[cask.d]) == nw[cask.c]) tc++;
}
int mx = max({ta, tb, tc});
if(mx < val)
{
val = mx;
vbest.clear();
vbest.pb(cask);
}
else if(mx == val)
{
vbest.pb(cask);
}
}
}
query best = vbest[(rand()) % sz(vbest)];
vector<vector<int> > next;
if(best.type == 0)
{
int ret = getHeaviest(best.a + 1, best.b + 1, best.c + 1) - 1;
for(auto nw: pos)
{
if(max({nw[best.a], nw[best.b], nw[best.c]}) == nw[ret]) next.pb(nw);
}
}
else if(best.type == 1)
{
int ret = getLightest(best.a + 1, best.b + 1, best.c + 1) - 1;
for(auto nw: pos)
{
if(min({nw[best.a], nw[best.b], nw[best.c]}) == nw[ret]) next.pb(nw);
}
}
else if(best.type == 2)
{
int ret = getMedian(best.a + 1, best.b + 1, best.c + 1) - 1;
for(auto nw: pos)
{
if(fi_median(nw[best.a], nw[best.b], nw[best.c]) == nw[ret]) next.pb(nw);
}
}
else
{
int ret = getNextLightest(best.a + 1, best.b + 1, best.c + 1, best.d + 1) - 1;
for(auto nw: pos)
{
if(fi_next_light(nw[best.a], nw[best.b], nw[best.c], nw[best.d]) == nw[ret]) next.pb(nw);
}
}
swap(pos, next);
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |