Submission #678902

#	Time	Username	Problem	Language	Result	Execution time	Memory
678902		n0sk1ll	Scales (IOI15_scales)	C++17	77.68 / 100	110 ms	468 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.

scales

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) (x).begin(),(x).end()
#define inv(n) power((n), mod - 2)
#define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
#define bff(i,a,b) for (int (i) = (b)-1; (i) >= (a); (i)--)
#define bfff(i,a,b) for (int (i) = (b); (i) >= (a); (i)--)
#define sum_overflow(a,b) __builtin_add_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)
#define mul_overflow(a,b) __builtin_mul_overflow_p ((a), (b), (__typeof__ ((a) + (b))) 0)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

/*int jp[6];

int getLightest(int a, int b, int c)
{
    int red=0;
    ff(i,0,6)
    {
        if (jp[i]==a || jp[i]==b || jp[i]==c)
        {
            if (red==0)
            {
                if (jp[i]==a) return a;
                if (jp[i]==b) return b;
                if (jp[i]==c) return c;
            }
            else red++;
        }
    }
}
int getMedian(int a, int b, int c)
{
    int red=0;
    ff(i,0,6)
    {
        if (jp[i]==a || jp[i]==b || jp[i]==c)
        {
            if (red==1)
            {
                if (jp[i]==a) return a;
                if (jp[i]==b) return b;
                if (jp[i]==c) return c;
            }
            else red++;
        }
    }
}
int getHeaviest(int a, int b, int c)
{
    int red=0;
    ff(i,0,6)
    {
        if (jp[i]==a || jp[i]==b || jp[i]==c)
        {
            if (red==2)
            {
                if (jp[i]==a) return a;
                if (jp[i]==b) return b;
                if (jp[i]==c) return c;
            }
            else red++;
        }
    }
}
int getNextLightest(int a, int b, int c, int d)
{
    int red=69;
    ff(i,0,6)
    {
        if (jp[i]==d) red=0;
        if (jp[i]==a || jp[i]==b || jp[i]==c)
        {
            if (red==0)
            {
                if (jp[i]==a) return a;
                if (jp[i]==b) return b;
                if (jp[i]==c) return c;
            }
            else red++;
        }
    }
    ff(i,0,6)
    {
        if (jp[i]==a || jp[i]==b || jp[i]==c)
        {
            if (red==0)
            {
                if (jp[i]==a) return a;
                if (jp[i]==b) return b;
                if (jp[i]==c) return c;
            }
            else red++;
        }
    }
}
void answer(int* sta)
{
    ff(i,0,6) cout<<jp[i]<<" "; cout<<endl;
    ff(i,0,6) cout<<sta[i]<<" "; cout<<endl;
    cout<<endl;
}*/

#include "scales.h"

vector<vector<int>> perms;

mt19937 rng(29042004);

void init(int T)
{
    perms.clear();
    vector<int> tperm={1,2,3,4,5,6};
    do
    {
        perms.pb(tperm);
    } while (next_permutation(all(tperm)));
}

int evalmin(int a, int b, int c)
{
    int ka=0,kb=0,kc=0;
    for (auto p : perms)
    {
        for (auto it : p)
        {
            if (it==a) {ka++; break;}
            if (it==b) {kb++; break;}
            if (it==c) {kc++; break;}
        }
    }
    return max(max(ka,kb),kc)-min(min(ka,kb),kc);
}

int evalmed(int a, int b, int c)
{
    int ka=0,kb=0,kc=0;
    for (auto p : perms)
    {
        int red=0;
        for (auto it : p)
        {
            if (it==a) {if (red==1) {ka++; break;} else red++;}
            if (it==b) {if (red==1) {kb++; break;} else red++;}
            if (it==c) {if (red==1) {kc++; break;} else red++;}
        }
    }
    return max(max(ka,kb),kc)-min(min(ka,kb),kc);
}

int evalmax(int a, int b, int c)
{
    int ka=0,kb=0,kc=0;
    for (auto p : perms)
    {
        int red=0;
        for (auto it : p)
        {
            if (it==a) {if (red==2) {ka++; break;} else red++;}
            if (it==b) {if (red==2) {kb++; break;} else red++;}
            if (it==c) {if (red==2) {kc++; break;} else red++;}
        }
    }
    return max(max(ka,kb),kc)-min(min(ka,kb),kc);
}

int evalwtf(int a, int b, int c, int d)
{
    int ka=0,kb=0,kc=0;
    for (auto p : perms)
    {
        int red=0; bool svrsio=0; bool oki=false;
        for (auto it : p)
        {
            if (it==a) {if (oki) {ka++; svrsio=1; break;}}
            if (it==b) {if (oki) {kb++; svrsio=1; break;}}
            if (it==c) {if (oki) {kc++; svrsio=1; break;}}
            if (it==d) oki=true;
        }
        if (!svrsio) for (auto it : p)
        {
            if (it==a) {ka++; break;}
            if (it==b) {kb++; break;}
            if (it==c) {kc++; break;}
        }
    }
    return max(max(ka,kb),kc)-min(min(ka,kb),kc);
}

int ans[6];
void orderCoins()
{
    if ((int)perms.size()==1)
    {
        ff(i,0,6) ans[i]=perms.back()[i];
        answer(ans),init(0);
        return;
    }

    vector<vector<int>> qrys;
    int sta=837339;

    fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
    {
        int tval;

        fff(_,1,6) if (_!=i && _!=j && _!=k)
        {
            tval=evalwtf(i,j,k,_);
            if (tval<sta) qrys.clear(),sta=tval;
            if (tval==sta) qrys.pb({4,i,j,k,_});
        }

        tval=evalmed(i,j,k);
        if (tval<sta) qrys.clear(),sta=tval;
        if (tval==sta) qrys.pb({2,i,j,k});

        tval=evalmin(i,j,k);
        if (tval<sta) qrys.clear(),sta=tval;
        if (tval==sta) qrys.pb({1,i,j,k});

        tval=evalmax(i,j,k);
        if (tval<sta) qrys.clear(),sta=tval;
        if (tval==sta) qrys.pb({3,i,j,k});
    }

    auto sezame=qrys[rng()%qrys.size()];

    vector<vector<int>> tmp;
    if (sezame[0]==1)
    {
        int a=sezame[1],b=sezame[2],c=sezame[3];
        int x=getLightest(a,b,c);
        for (auto p : perms)
        {
            for (auto it : p)
            {
                if (it==a) {if (it==x) tmp.pb(p); break;}
                if (it==b) {if (it==x) tmp.pb(p); break;}
                if (it==c) {if (it==x) tmp.pb(p); break;}
            }
        }
    }
    if (sezame[0]==2)
    {
        int a=sezame[1],b=sezame[2],c=sezame[3];
        int x=getMedian(a,b,c);
        for (auto p : perms)
        {
            int red=0;
            for (auto it : p)
            {
                if (it==a) {if (red==1) {if (it==x) tmp.pb(p); break;} else red++;}
                if (it==b) {if (red==1) {if (it==x) tmp.pb(p); break;} else red++;}
                if (it==c) {if (red==1) {if (it==x) tmp.pb(p); break;} else red++;}
            }
        }
    }
    if (sezame[0]==3)
    {
        int a=sezame[1],b=sezame[2],c=sezame[3];
        int x=getHeaviest(a,b,c);
        for (auto p : perms)
        {
            int red=0;
            for (auto it : p)
            {
                if (it==a) {if (red==2) {if (it==x) tmp.pb(p); break;} else red++;}
                if (it==b) {if (red==2) {if (it==x) tmp.pb(p); break;} else red++;}
                if (it==c) {if (red==2) {if (it==x) tmp.pb(p); break;} else red++;}
            }
        }
    }
    if (sezame[0]==4)
    {
        int a=sezame[1],b=sezame[2],c=sezame[3],d=sezame[4];
        int x=getNextLightest(a,b,c,d);
        for (auto p : perms)
        {
            int red=0; bool svrsio=0; bool oki=false;
            for (auto it : p)
            {
                if (it==a) {if (oki) {if (it==x) tmp.pb(p); svrsio=1; break;}}
                if (it==b) {if (oki) {if (it==x) tmp.pb(p); svrsio=1; break;}}
                if (it==c) {if (oki) {if (it==x) tmp.pb(p); svrsio=1; break;}}
                if (it==d) oki=true;
            }
            if (!svrsio) for (auto it : p)
            {
                if (it==a) {if (it==x) tmp.pb(p); break;}
                if (it==b) {if (it==x) tmp.pb(p); break;}
                if (it==c) {if (it==x) tmp.pb(p); break;}
            }
        }
    }
    perms=tmp;

    /*for (auto p : perms)
    {
        cout<<"jbt ";
        for (auto it : p) cout<<it<<" ";
        cout<<endl;
    } cout<<endl;*/

    orderCoins();
}

/*int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    int t; cin>>t;
    init(t);

    ff(i,0,6) jp[i]=i+1;

    while (t--)
    {
        orderCoins();
        next_permutation(jp,jp+6);
    }
}*/

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:137:15: warning: unused parameter 'T' [-Wunused-parameter]
  137 | void init(int T)
      |           ~~~~^
scales.cpp: In function 'int evalwtf(int, int, int, int)':
scales.cpp:199:13: warning: unused variable 'red' [-Wunused-variable]
  199 |         int red=0; bool svrsio=0; bool oki=false;
      |             ^~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:13:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   13 | #define ff(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
      |                            ^
scales.cpp:222:9: note: in expansion of macro 'ff'
  222 |         ff(i,0,6) ans[i]=perms.back()[i];
      |         ^~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
scales.cpp:230:5: note: in expansion of macro 'fff'
  230 |     fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
      |     ^~~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
scales.cpp:230:16: note: in expansion of macro 'fff'
  230 |     fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
      |                ^~~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
scales.cpp:230:29: note: in expansion of macro 'fff'
  230 |     fff(i,1,6) fff(j,i+1,6) fff(k,j+1,6)
      |                             ^~~
scales.cpp:14:29: warning: unnecessary parentheses in declaration of '_' [-Wparentheses]
   14 | #define fff(i,a,b) for (int (i) = (a); (i) <= b; (i)++)
      |                             ^
scales.cpp:234:9: note: in expansion of macro 'fff'
  234 |         fff(_,1,6) if (_!=i && _!=j && _!=k)
      |         ^~~
scales.cpp:307:17: warning: unused variable 'red' [-Wunused-variable]
  307 |             int red=0; bool svrsio=0; bool oki=false;
      |                 ^~~

Subtask 177.678571 / 100

#	Verdict	Execution time	Memory	Grader output
Fetching results...