Submission #411931

#	Time	Username	Problem	Language	Result	Execution time	Memory
411931		losmi247	Scales (IOI15_scales)	C++14	38.46 / 100	1 ms	224 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 7;



/*int *p;
int gde[N];
void answer(int *sta){
    for(int i = 0; i < 6; i++){
        if(sta[i] != p[i]){
            cout << "WA" << endl;
            exit(0);
        }
    }
    cout << "OK" << endl;
}

int getHeaviest(int a,int b,int c){
    vector <int> v = {gde[a],gde[b],gde[c]};
    sort(v.begin(),v.end());
    return p[v[2]];
}

int getLightest(int a,int b,int c){
    vector <int> v = {gde[a],gde[b],gde[c]};
    sort(v.begin(),v.end());
    return p[v[0]];
}

int getMedian(int a,int b,int c){
    vector <int> v = {gde[a],gde[b],gde[c]};
    sort(v.begin(),v.end());
    return p[v[1]];
}

int getNextLightest(int a,int b,int c,int d){
    if(gde[a] < gde[d] && gde[b] < gde[d] && gde[c] < gde[d]) return getLightest(a,b,c);
    vector <int> v;
    if(gde[a] > gde[d]) v.push_back(gde[a]);
    if(gde[b] > gde[d]) v.push_back(gde[b]);
    if(gde[c] > gde[d]) v.push_back(gde[c]);
    sort(v.begin(),v.end());
    return p[v[0]];
}*/





int t;
int n = 6;

void init(int T){
    t = T;
}

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

vector <int> jedanpojedan(){
    vector <int> v;
    for(int i = 1; i <= n; i++) v.push_back(i);

    vector <int> odg;
    while(v.size() > 3){
        vector <int> red;
        for(int i = 0; i < v.size(); i++) red.push_back(i);
        //shuffle(red.begin(),red.end(),rnd);

        for(int h = 0; h < red.size(); h++){
            int i = red[h];
            int ovaj = v[i];
            int drugi = -1,pos = 0;
            for(int j = 0; j < v.size(); j++){
                if(j == i) continue;
                drugi = v[j];
                pos = j;
            }
            bool jestenajmanji = 1;
            for(int j = 0; j < v.size(); j++){
                if(j == i || j == pos) continue;
                int daj = getLightest(v[i],drugi,v[j]);
                if(daj != v[i]){
                    jestenajmanji = 0;
                    break;
                }
            }
            if(jestenajmanji){
                odg.push_back(v[i]);
                vector <int> cuv;
                while(v.back() != v[i]){
                    cuv.push_back(v.back());
                    v.pop_back();
                }
                v.pop_back();
                reverse(cuv.begin(),cuv.end());
                for(auto f : cuv){
                    v.push_back(f);
                }
                break;
            }
        }
    }

    int najm = getLightest(v[0],v[1],v[2]), sred = getMedian(v[0],v[1],v[2]), najv = getHeaviest(v[0],v[1],v[2]);

    odg.push_back(najm);
    odg.push_back(sred);
    odg.push_back(najv);

    return odg;
}

int najlaksiodsest(vector <int> v){   /// 3 op
    int s1 = getLightest(v[0],v[1],v[2]),s2 = getLightest(v[3],v[4],v[5]);
    int nekidrugi = -1;
    for(int j = 0; j < 6; j++){
        if(v[j] == s1 || v[j] == s2) continue;
        nekidrugi = v[j];
    }
    int s3 = getLightest(s1,s2,nekidrugi);
    return s3;
}

int najlaksiodpet(vector <int> v){   /// 3 op
    int s1 = getLightest(v[0],v[1],v[2]),s2 = getLightest(v[2],v[3],v[4]);
    if(s1 == s2) return s1;
    int nekidrugi = -1;
    for(int j = 0; j < 5; j++){
        if(v[j] == s1 || v[j] == s2) continue;
        nekidrugi = v[j];
    }
    int s3 = getLightest(s1,s2,nekidrugi);
    return s3;
}

int najlaksiodcetri(vector <int> v){  /// 2 op
    int s1 = getLightest(v[0],v[1],v[2]);
    int nekidrugi = -1;
    for(int j = 0; j < 3; j++){
        if(v[j] == s1) continue;
        nekidrugi = v[j];
    }
    int s2 = getLightest(nekidrugi,s1,v[3]);
    return s2;
}

void izbaci(vector <int> &g,int sta){
    vector <int> cuv;
    while(g.back() != sta){
        cuv.push_back(g.back());
        g.pop_back();
    }
    g.pop_back();
    reverse(cuv.begin(),cuv.end());
    for(auto f : cuv) g.push_back(f);
}

vector <int> nestodrugo(){ /// 10 ops max
    vector <int> v;
    for(int i = 1; i <= 6; i++) v.push_back(i);
    if(rnd()%2) reverse(v.begin(),v.end());

    vector <int> odg;

    int d = najlaksiodsest(v);
    odg.push_back(d);
    izbaci(v,d);

    d = najlaksiodpet(v);
    odg.push_back(d);
    izbaci(v,d);

    d = najlaksiodcetri(v);
    odg.push_back(d);
    izbaci(v,d);

    int najm = getLightest(v[0],v[1],v[2]), sred = getMedian(v[0],v[1],v[2]);
    int najv = -1;
    for(int i = 0; i < 3; i++){
        if(v[i] == najm || v[i] == sred) continue;
        najv = v[i];
    }

    odg.push_back(najm);
    odg.push_back(sred);
    odg.push_back(najv);

    return odg;
}

void orderCoins(){
    vector <int> v = /*jedanpojedan()*/ nestodrugo();
    int *ans = (int*)malloc(sizeof(int)*6);
    for(int i = 0; i < 6; i++) ans[i] = v[i];
    answer(ans);
}



/*int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tc;
    cin >> tc;
    init(tc);
    for(int i = 1; i <= tc; i++){
        p = (int*)malloc(sizeof(int)*6);
        for(int j = 0; j < 6; j++){ cin >> p[j]; gde[p[j]] = j; }
        orderCoins();
    }
}*/

Compilation message (stderr)

scales.cpp: In function 'std::vector<int> jedanpojedan()':
scales.cpp:69:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for(int i = 0; i < v.size(); i++) red.push_back(i);
      |                        ~~^~~~~~~~~~
scales.cpp:72:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for(int h = 0; h < red.size(); h++){
      |                        ~~^~~~~~~~~~~~
scales.cpp:76:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(int j = 0; j < v.size(); j++){
      |                            ~~^~~~~~~~~~
scales.cpp:82:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for(int j = 0; j < v.size(); j++){
      |                            ~~^~~~~~~~~~
scales.cpp:74:17: warning: unused variable 'ovaj' [-Wunused-variable]
   74 |             int ovaj = v[i];
      |                 ^~~~

• Subtask 1: 38.461538 / 100