| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 286308 | abyyskit | Scales (IOI15_scales) | C++14 | 319 ms | 664 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<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
vector<vector<int>> UNI;
vector<vector<int>> Q;
void init(int T) {
// cout << "starting preprocessing\n";
vector<int> tmp = {1, 2, 3, 4, 5, 6};
UNI.pb(tmp);
while(next_permutation(tmp.begin(), tmp.end())){
UNI.pb(tmp);
}
FOR(i, 1, 7){
FOR(j, i + 1, 7){
FOR(k, j + 1, 7){
FOR(ii, 0, 3){
Q.pb({i, j, k, ii});
Q.pb({i, k, j, ii});
Q.pb({j, i, k, ii});
Q.pb({j, k, i, ii});
Q.pb({k, j, i, ii});
Q.pb({k, i, j, ii});
}
}
}
}
set<vector<int>> s;
FOR(i, 0, UNI.size()){
vector<int> TMP = {UNI[i][0], UNI[i][1], UNI[i][2], UNI[i][3], 0};
if (s.count(TMP) == 0){
s.insert(TMP);
Q.pb(TMP);
}
}
// cout << "preprocessed\n";
return;
}
int qans(vector<int>& q, vector<int>& pos){
if (q.size() == 4){
if (q.back() == 0){
//smallest
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[i] == q[j]){
return q[j];
}
}
}
}
else if (q.back() == 2){
//largest
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[5 - i] == q[j]){
return q[j];
}
}
}
}
else{
//median
bool flag = false;
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[i] == q[j]){
if (flag){
return q[j];
}
else{
flag = true;
}
}
}
}
}
}
//4 coins on scale
int small = -1;
bool flag = false;
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[i] == q[j]){
if (small == -1){
small = q[j];
}
if (flag){
return q[j];
}
}
}
if (pos[i] == q[3]){
flag = true;
}
}
return small;
}
pair<int, long double> value(vector<int>& q, vector<vector<int>>& uni){
vector<int> dist(6);
FOR(i, 0, uni.size()){
dist[qans(q, uni[i]) - 1]++;
}
int ans = 0;
long double ans2 = 0;
FOR(i, 0, dist.size()){
ans2 += dist[i]*dist[i];
if (dist[i] > ans){
ans = dist[i];
}
}
ans2 = sqrt(ans2/3);
return {ans, ans2};
}
void orderCoins() {
/* ... */
int C = 0;
vector<vector<int>> uni = UNI;
// cout << Q.size() << "\n";
// vector<int> test = {3, 4, 6, 2, 1, 5};
while(uni.size() > 1){
// cout << C << "\n";
C++;
vector<pair<int, long double>> qv(Q.size());
FOR(i, 0, Q.size()){
qv[i] = value(Q[i], uni);
}
// cout << "values calculated\n";
int ind = 0;
pair<int, long double> ans = qv[0];
FOR(i, 0, qv.size()){
if (qv[i].first < ans.first){
ans = qv[i];
ind = i;
}
if (qv[i].first == ans.first){
if (qv[i].second < ans.second){
ans = qv[i];
ind = i;
}
}
}
// if (uni.size() == 720){
// ind = 669;
// }
// cout << ans.first << " " << ans.second << "\n";
int A;
if (Q[ind].size() == 4){
if (Q[ind].back() == 0){
A = getLightest(Q[ind][0], Q[ind][1], Q[ind][2]);
}
else if (Q[ind].back() == 2){
A = getHeaviest(Q[ind][0], Q[ind][1], Q[ind][2]);
}
else{
A = getMedian(Q[ind][0], Q[ind][1], Q[ind][2]);
}
}
else{
A = getNextLightest(Q[ind][0], Q[ind][1], Q[ind][2], Q[ind][3]);
}
// cout << "A = " << A << "\n";
vector<vector<int>> Nuni;
FOR(i, 0, uni.size()){
if (qans(Q[ind], uni[i]) == A){
Nuni.pb(uni[i]);
}
}
swap(Nuni, uni);
/* cout << "uni: " << uni.size() << "\n";
FOR(i, 0, Q[ind].size()){
cout << Q[ind][i] << " ";
}
cout << "\n";
cout << qans(Q[ind], test) << "\n";
cout << "end\n";*/
}
//cout << "Done\n";
int W[] = {uni[0][0], uni[0][1], uni[0][2], uni[0][3], uni[0][4], uni[0][5]};
/* cout << "Answer is: ";
FOR(i, 0, 6){
cout << W[i] << " ";
}
cout << "\n";*/
answer(W);
return;
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||