| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 824074 | Khizri | 저울 (IOI15_scales) | C++17 | 5 ms | 5464 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=2e5+5;
vector<vector<int>>vt[mxn];
int L[mxn],R[mxn],M[mxn],iq[mxn],jq[mxn],kq[mxn],op[mxn],nxt=1;
void build(int node){
ll mx=INF;
int ix,jx,kx;
for(int i=0;i<6;i++){
for(int j=i+1;j<6;j++){
for(int k=j+1;k<6;k++){
ll a=0,b=0,c=0;
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][i]>max(vt[node][idx][j],vt[node][idx][k])){
a++;
}
else if(vt[node][idx][j]>max(vt[node][idx][i],vt[node][idx][k])){
b++;
}
else{
c++;
}
}
if(max(a,max(b,c))<mx){
mx=max(a,max(b,c));
op[node]=1;
ix=i,jx=j,kx=k;
}
}
}
}
for(int i=0;i<6;i++){
for(int j=i+1;j<6;j++){
for(int k=j+1;k<6;k++){
ll a=0,b=0,c=0;
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][i]<min(vt[node][idx][j],vt[node][idx][k])){
a++;
}
else if(vt[node][idx][j]<min(vt[node][idx][i],vt[node][idx][k])){
b++;
}
else{
c++;
}
}
if(max(a,max(b,c))<mx){
mx=max(a,max(b,c));
op[node]=0;
ix=i,jx=j,kx=k;
}
}
}
}
L[node]=++nxt;
M[node]=++nxt;
R[node]=++nxt;
iq[node]=ix;
jq[node]=jx;
kq[node]=kx;
if(op[node]==1){
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][ix]>max(vt[node][idx][jx],vt[node][idx][kx])){
vt[L[node]].pb(vt[node][idx]);
}
else if(vt[node][idx][jx]>max(vt[node][idx][ix],vt[node][idx][kx])){
vt[M[node]].pb(vt[node][idx]);
}
else{
vt[R[node]].pb(vt[node][idx]);
}
}
}
else{
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][ix]<min(vt[node][idx][jx],vt[node][idx][kx])){
vt[L[node]].pb(vt[node][idx]);
}
else if(vt[node][idx][jx]<min(vt[node][idx][ix],vt[node][idx][kx])){
vt[M[node]].pb(vt[node][idx]);
}
else{
vt[R[node]].pb(vt[node][idx]);
}
}
}
if(vt[L[node]].size()>1){
build(L[node]);
}
if(vt[M[node]].size()>1){
build(M[node]);
}
if(vt[R[node]].size()>1){
build(R[node]);
}
}
vector<int>query(int node){
if(vt[node].size()==1){
return vt[node][0];
}
int x;
if(op[node]==1){
x=getHeaviest(iq[node]+1,jq[node]+1,kq[node]+1);
}
else{
x=getLightest(iq[node]+1,jq[node]+1,kq[node]+1);
}
if(x==iq[node]+1){
return query(L[node]);
}
else if(x==jq[node]+1){
return query(M[node]);
}
else{
return query(R[node]);
}
}
void init(int T) {
vector<int>v(6);
iota(all(v),1);
do{
vt[1].pb(v);
}while(next_permutation(all(v)));
build(1);
}
void orderCoins() {
vector<int>vt=query(1);
int arr[6];
for(int i=0;i<6;i++){
arr[vt[i]-1]=i+1;
}
answer(arr);
}
/*
g++ scales.cpp grader.cpp ; .\a.exe
*/
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||