| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 532702 | ivan24 | Scales (IOI15_scales) | C++14 | 0 ms | 0 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;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
ll min (ll x, ll y){
return ((x < y) ? x : y);
}
ll max (ll x, ll y){
return ((x > y) ? x : y);
}
const ll INF = 1e18;
class Solution {
private:
vi w;
vi idx;
public:
Solution (){
}
Solution (vi _w): w(_w){
idx.resize(7);
for (ll i = 0; 6 > i; i++) idx[w[i]] = i;
}
ll test (ll type, vi params){
if (3 > type){
vii v;
for (auto i: params) v.emplace_back(idx[i],i);
sort(v.begin(),v.end());
return v[type].S;
}else{
vii v;
for (auto i: params) v.emplace_back(idx[i],i);
v.pop_back();
sort(v.begin(),v.end());
ll target = idx[params[3]];
for (ll i = 0; v.size() > i; i++){
if (v[i].F > target) return v[i].S;
}
return v[0].S;
}
}
vi get_w(){
return w;
}
};
class SolutionSet {
private:
vector<Solution> space;
vector<pair<ll,vi> > history;
ll try_test (ll type, vi params) {
ll res = 0;
vi vcur; vcur.assign(7,0);
for (auto i: space){
ll cur = i.test(type,params);
vcur[cur]++;
}
for (auto i: vcur) res += i*i;
return res;
}
public:
SolutionSet(){
vi cur_w;
for (ll i = 0; 6 > i; i++) cur_w.push_back(i+1);
do{
space.push_back(Solution(cur_w));
}while (next_permutation(cur_w.begin(),cur_w.end()));
}
ll get_size(){
return space.size();
}
void best_test(){
ll cur = INF, curt;
vi curparam;
for (ll t = 0; 3 > t; t++){
for (ll i = 1; 6 >= i; i++){
for (ll j = i+1; 6 >= j; j++){
for (ll k = j+1; 6 >= k; k++){
ll curscore = try_test(t,vi{i,j,k});
if (curscore < cur){
cur = curscore; curt = t; curparam = vi{i,j,k};
}
}
}
}
}
for (ll i = 1; 6 >= i; i++){
for (ll j = i+1; 6 >= j; j++){
for (ll k = j+1; 6 >= k; k++){
for (ll o = 1; 6 >= o; o++){
if ((o == i) || (o == j) || (o == k)) continue;
ll curscore = try_test(3,vi{i,j,k,o});
if (curscore < cur){
cur = curscore; curt = 3; curparam = vi{i,j,k,o};
}
}
}
}
}
ll res;
if (curt == 0){
res = getLightest(curparam[0],curparam[1],curparam[2]);
}else if (curt == 1){
res = getMedian(curparam[0],curparam[1],curparam[2]);
}else if (curt == 2){
res = getHeaviest(curparam[0],curparam[1],curparam[2]);
}else
res = getNextLightest(curparam[0],curparam[1],curparam[2],curparam[3]);
vector<Solution> newspace;
for (auto i: space){
if (i.test(curt,curparam) == res) newspace.push_back(i);
}
space = newspace;
}
vi answer(){
return space[0].get_w();
}
};
void init(int t) {
/* ... */
}
void orderCoins() {
/* ... */
SolutionSet mySol;
while (mySol.get_size() != 1){
mySol.best_test();
}
vi res = mySol.answer();
int w[] = {1,2,3,4,5,6};
for (ll i = 0; 6 > i; i++) w[i] = res[i];
answer(w);
/*
ll p_r = 0, p_l = 0;
while (p_r != 3 || p_l != 3){
if (p_r == 3){
w[p_l+p_r] = l_ar[p_l];
p_l++;
}else if (p_l == 3){
w[p_l+p_r] = r_ar[p_r];
p_r++;
}else{
ll cur;
if (p_l == 2 && p_r == 2){
cur = getMedian(l_ar[1],l_ar[2],r_ar[2]);
}else if (p_r == 2){
cur = getLightest(l_ar[p_l],l_ar[p_l+1],r_ar[p_r]);
}else if (p_l == 2){
cur = getLightest(l_ar[p_l],r_ar[p_r+1],r_ar[p_r]);
}else{
cur = getLightest(l_ar[p_l],r_ar[p_r+1],r_ar[p_r]);
}
w[p_l+p_r] = cur;
if (cur == l_ar[p_l]){
p_l++;
}else{
p_r++;
}
}
}
w[5] = 21;
for (ll i = 0; 4 >= i; i++) w[5] -= w[i];
*/
answer(w);
}
#include "graderlib.c"
int main() {
int T, i;
T = _getNumberOfTests();
init(T);
for (i = 1; i <= T; i++) {
_initNewTest();
orderCoins();
}
return 0;
}