| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1061849 | anango | 저울 (IOI15_scales) | C++17 | 983 ms | 856 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define map unordered_map
mt19937 rng;
int INF = 1<<30;
int testcases;
vector<vector<int>> permutations = {{1,2,3,4,5,6}};
vector<vector<int>> combvals={{1,2,3},{1,2,4},{1,2,5},{1,2,6},{1,3,4},{1,3,5},{1,3,6},{1,4,5},{1,4,6},{1,5,6},{2,3,4},{2,4,5},{2,3,5},{2,3,6},{2,4,6},{2,5,6},{3,4,5},{3,5,6},{3,4,6},{4,5,6}};
vector<vector<int>> combvals2={{1,2,3,4},{1,2,3,5},{1,2,3,6},{1,2,4,5},{1,2,4,6},{1,2,5,6},{1,3,4,5},{1,3,5,6},{1,3,4,6},{1,4,5,6},{2,3,4,5},{2,3,4,6},{2,3,5,6},{2,4,5,6},{3,4,5,6}};
vector<vector<int>> operations;
void init(int T) {
for (int i=0; i<719; i++) {
permutations.push_back(permutations.back());
next_permutation(permutations.back().begin(), permutations.back().end());
}
assert(permutations.size()==720);
assert(combvals.size()==20);
assert(combvals2.size()==15);
/* ... */
//initialise operations, each operation is id,a,b,c,d
for (int id=1; id<=3; id++) {
for (auto j:combvals) {
operations.push_back({id,j[0],j[1],j[2],-1});
}
}
for (auto j:combvals2) {
operations.push_back({4,j[0],j[1],j[2],j[3]});
}
testcases = T;
}
int apply_operation(vector<int> perm, int id, int a, int b, int c, int d) {
vector<int> pos(7); for (int i=0; i<6; i++) pos[perm[i]] = i;
vector<int> val = {a,b,c};
if (id==1) {
sort(val.begin(), val.end(), [&](const int i1, const int i2) {
return pos[i1]>pos[i2];
});
return val[0];
}
else if (id==2) {
sort(val.begin(), val.end(), [&](const int i1, const int i2) {
return pos[i1]<pos[i2];
});
return val[0];
}
else if (id==3) {
sort(val.begin(), val.end(), [&](const int i1, const int i2) {
return pos[i1]<pos[i2];
});
return val[1];
}
else if (id==4) {
sort(val.begin(), val.end(), [&](const int i1, const int i2) {
return (pos[i1]<pos[i2] && !(pos[i1]<pos[d] && pos[d]<pos[i2])) || (pos[i1]>pos[d] && pos[d]>pos[i2]);
});
return val[0];
}
return 88888888;
}
void prv(vector<int> v) {
for (auto i:v) {
cout << i <<" ";
}
cout << endl;
}
int operate(vector<int> v) {
if (v[0]==1) {
return getHeaviest(v[1],v[2],v[3]);
}
if (v[0]==2) {
return getLightest(v[1],v[2],v[3]);
}
if (v[0]==3) {
return getMedian(v[1],v[2],v[3]);
}
if (v[0]==4) {
return getNextLightest(v[1],v[2],v[3],v[4]);
}
return 88888888;
}
vector<int> pow3 = {1,3,9,27,81,243,729};
bool workable(vector<vector<int>> poss, int depth) {
//cout << "working " << poss.size() <<" " << depth << endl;
if (poss.size()>pow3[depth]) return 0;
if (depth<=1) return 1;
int minrval=INF;
for (auto operation:operations) {
map<int,int> freq;
map<int,vector<vector<int>>> S;
for (auto j:poss) {
int val = apply_operation(j,operation[0],operation[1],operation[2],operation[3],operation[4]);
freq[val]++;
S[val].push_back(j);
}
int mval = -1;
for (auto j:freq) {
mval=max(mval,j.second);
}
if (mval>pow3[depth-1]) {
continue;
}
int fail = 0;
for (auto j:S) {
if (!workable(j.second,depth-1)) {
fail=1;
}
}
if (fail) continue;
minrval = mval;
break;
}
if (minrval==INF) return 0;
return 1;
}
void orderCoins() {
auto start = std::chrono::high_resolution_clock::now();
/* ... */
vector<vector<int>> poss(permutations.begin(), permutations.end());
int depth = 5;
while (poss.size()>1) {
vector<vector<int>> minrops;
vector<int> minrop;
int minrval = INF; //minimise the maximum
for (auto operation:operations) {
map<int,int> freq;
map<int,vector<vector<int>>> S;
for (auto j:poss) {
int val = apply_operation(j,operation[0],operation[1],operation[2],operation[3],operation[4]);
freq[val]++;
S[val].push_back(j);
}
int mval = -1;
for (auto j:freq) {
mval=max(mval,j.second);
}
if (mval>pow3[depth]) {
continue;
}
int fail = 0;
for (auto j:S) {
if (!workable(j.second,depth)) {
fail=1;
}
}
if (fail) continue;
minrop = operation;
minrops.push_back(minrop);
minrval = mval;
break;
}
//cout << "MINIMAL OPERATION" << " " << minrops.size() << endl;
//prv(minrop);
minrop = minrops[rng()%((int)minrops.size())];
minrop = minrops[0];
minrop = minrops[minrops.size()/2];
int opans = operate(minrop);
//cout << minrval << " " << opans << endl;
//cout << "reducing " << minrval << endl;
vector<vector<int>> newposs;
for (auto j:poss) {
int val = apply_operation(j,minrop[0],minrop[1],minrop[2],minrop[3],minrop[4]);
if (val==opans) {
newposs.push_back(j);
}
}
poss=newposs;
depth--;
}
vector<int> ans = *poss.begin();
int a = ans[0]; int b = ans[1]; int c = ans[2]; int d = ans[3]; int e = ans[4]; int f = ans[5];
int W[6] = {a,b,c,d,e,f};
auto end = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> duration = end - start;
//std::cout << "Time taken: " << duration.count() << " seconds" << std::endl;
answer(W);
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||