| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 982149 | XCAC197 | Scales (IOI15_scales) | C++14 | 273 ms | 1204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "scales.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
vector <vector<int>> pos;
vector <vector <int>> q;
void query(int atr){
int ans = 0;
if(q[atr][4] == 3){
ans = getNextLightest(q[atr][0], q[atr][1], q[atr][2], q[atr][3]);
}else{
if(q[atr][4] == 0){
ans = getLightest(q[atr][0], q[atr][1], q[atr][2]);
}else if(q[atr][4] == 1){
ans = getMedian(q[atr][0], q[atr][1], q[atr][2]);
}else{
ans = getHeaviest(q[atr][0], q[atr][1], q[atr][2]);
}
}
// cout << ans << endl;
int res = -1;
for(int i = 0; i < 3; i++){
if(ans == q[atr][i]){
res = i;
}
}
/* cout << atr << " " << res << endl;
for(int i = 0; i < 5; i++){
cout << q[atr][i] << " ";
}
cout << endl;*/
vector <vector<int>> newPos;
for(int i = 0; i < pos.size(); i++){
if(pos[i][atr] == res){
newPos.push_back(pos[i]);
}
}
pos = newPos;
}
void init(int T) {
for(int i = 0; i < 6; i++){
for(int j = i+1; j < 6; j++){
for(int k = j+1; k < 6; k++){
q.push_back({i+1, j+1, k+1, 0, 0});
q.push_back({i+1, j+1, k+1, 0, 1});
q.push_back({i+1, j+1, k+1, 0, 2});
for(int l = 0; l < 6; l++){
if((l != i) && (l != j) && (l != k)){
q.push_back({i+1, j+1, k+1, l+1, 3});
}
}
}
}
}
}
int atLeast(int x){
int bestFeasable = 0;
int cur = 1;
while(cur < x){
bestFeasable++;
cur *= 3;
}
return bestFeasable;
}
pair <int,int> dfs(vector <vector <int>> v){
if(v.size() <= 1){
return make_pair(0, 0);
}else{
vector <pair<int, int>> ent;
for(int i = 0; i < 120; i++){
int cnt [3] = {0, 0, 0};
for(int j = 0; j < v.size(); j++){
cnt[v[j][i]]++;
}
int biggest = 0;
for(int j = 0; j < 3; j++){
biggest = max(biggest, cnt[j]);
}
ent.push_back(make_pair(biggest, i));
}
sort(ent.begin(), ent.end());
int best = 999;
int bestInd = 0;
for(int ind = 0; ind < 120; ind++){
if((atLeast(ent[ind].first)+1) < best){
int i = ent[ind].second;
vector <vector<int>> cat [3];
for(int j = 0; j < v.size(); j++){
cat[v[j][i]].push_back(v[j]);
}
int mxSiz = 0;
for(int j = 0; j < 3; j++){
mxSiz = max(mxSiz, (int)(cat[j].size()));
}
if(mxSiz != v.size()){
int mx = 0;
for(int j = 0; j < 3; j++){
mx = max(mx, dfs(cat[j]).first);
}
if((mx+1) < best){
bestInd = i;
best = mx+1;
}
if(best == atLeast(v.size())){
break;
}
}
}else{
break;
}
}
return make_pair(best, bestInd);
}
}
void orderCoins() {
pos.clear();
vector <int> perm = {1, 2, 3, 4, 5, 6};
do{
vector <int> v;
for(int i = 0; i < 6; i++){
for(int j = i+1; j < 6; j++){
for(int k = j+1; k < 6; k++){
vector <pair<int,int>> abc;
abc.push_back(make_pair(perm[i], 0));
abc.push_back(make_pair(perm[j], 1));
abc.push_back(make_pair(perm[k], 2));
sort(abc.begin(), abc.end());
v.push_back(abc[0].second);
v.push_back(abc[1].second);
v.push_back(abc[2].second);
for(int l = 0; l < 6; l++){
if((l != i) && (l != j) && (l != k)){
for(int o = 0; o < 4; o++){
if((o == 3) || (perm[l] < abc[o].first)){
v.push_back(abc[o%3].second);
break;
}
}
}
}
}
}
}
/*for(int i = 0; i < 6; i++){
cout << perm[i] << " ";
}
cout << endl;
for(int i = 0; i < 120; i++){
cout << v[i] << " ";
}
cout << endl;*/
pos.push_back(v);
}while(next_permutation(perm.begin(), perm.end()));
// cout << "BING CHILLING" << endl;
query(0);
while(pos.size() != 1){
pair<int,int> p = dfs(pos);
query(p.second);
}
// cout << "BING CHILLING" << endl;
perm = {1, 2, 3, 4, 5, 6};
do{
vector <int> v;
for(int i = 0; i < 6; i++){
for(int j = i+1; j < 6; j++){
for(int k = j+1; k < 6; k++){
vector <pair<int,int>> abc;
abc.push_back(make_pair(perm[i], 0));
abc.push_back(make_pair(perm[j], 1));
abc.push_back(make_pair(perm[k], 2));
sort(abc.begin(), abc.end());
v.push_back(abc[0].second);
v.push_back(abc[1].second);
v.push_back(abc[2].second);
for(int l = 0; l < 6; l++){
if((l != i) && (l != j) && (l != k)){
for(int o = 0; o < 4; o++){
if((o == 3) || (perm[l] < abc[o].first)){
v.push_back(abc[o%3].second);
break;
}
}
}
}
}
}
}
bool same = true;
for(int i = 0; i < 120; i++){
if(v[i] != pos[0][i]){
same = false;
}
}
if(same){
int arr [6];
for(int i = 0; i < perm.size(); i++){
arr[perm[i]-1] = i+1;
}
// cout << "BING CHILLING" << endl;
answer(arr);
return;
}
}while(next_permutation(perm.begin(), perm.end()));
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||