제출 #678917

#제출 시각아이디문제언어결과실행 시간메모리
678917n0sk1llScales (IOI15_scales)C++14
100 / 100
386 ms237024 KiB
#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

#include "scales.h"

vector<vector<int>> perms;
mt19937 rng(29042004);

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 idx=1;
int g[10000007][3];
vector<int> stapitam[10000007]; //ne pitam nista ako znam odgovor

bool generate_tree(int p, vector<vector<int>> sperms, int d)
{
    //cout<<p<<" "<<sperms.size()<<" "<<d<<endl;
    if (d>=7) return false;
    if (sperms.size()==1)
    {
        stapitam[p]=sperms.back();
        return true;
    }
    if (sperms.empty()) return true;

    perms=sperms;
    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});
    }

    shuffle(all(qrys),rng);

    int upito=0;
    for (auto qq : qrys)
    {
        if (upito>sperms.size()/80+5) return false;
        upito++;

        stapitam[p]=qq;
        vector<vector<int>> gde1,gde2,gde3;

        if (qq[0]==1)
        {
            int a=qq[1],b=qq[2],c=qq[3];
            for (auto p : sperms)
            {
                for (auto it : p)
                {
                    if (it==a) {gde1.pb(p); break;}
                    if (it==b) {gde2.pb(p); break;}
                    if (it==c) {gde3.pb(p); break;}
                }
            }
        }
        if (qq[0]==2)
        {
            int a=qq[1],b=qq[2],c=qq[3];
            for (auto p : sperms)
            {
                int red=0;
                for (auto it : p)
                {
                    if (it==a) {if (red==1) {gde1.pb(p); break;} else red++;}
                    if (it==b) {if (red==1) {gde2.pb(p); break;} else red++;}
                    if (it==c) {if (red==1) {gde3.pb(p); break;} else red++;}
                }
            }
        }
        if (qq[0]==3)
        {
            int a=qq[1],b=qq[2],c=qq[3];
            for (auto p : sperms)
            {
                int red=0;
                for (auto it : p)
                {
                    if (it==a) {if (red==2) {gde1.pb(p); break;} else red++;}
                    if (it==b) {if (red==2) {gde2.pb(p); break;} else red++;}
                    if (it==c) {if (red==2) {gde3.pb(p); break;} else red++;}
                }
            }
        }
        if (qq[0]==4)
        {
            int a=qq[1],b=qq[2],c=qq[3],d=qq[4];
            for (auto p : sperms)
            {
                int red=0; bool svrsio=0; bool oki=false;
                for (auto it : p)
                {
                    if (it==a) {if (oki) {gde1.pb(p); svrsio=1; break;}}
                    if (it==b) {if (oki) {gde2.pb(p); svrsio=1; break;}}
                    if (it==c) {if (oki) {gde3.pb(p); svrsio=1; break;}}
                    if (it==d) oki=true;
                }
                if (!svrsio) for (auto it : p)
                {
                    if (it==a) {gde1.pb(p); break;}
                    if (it==b) {gde2.pb(p); break;}
                    if (it==c) {gde3.pb(p); break;}
                }
            }
        }

        //cout<<qq[0]<<" ? "<<gde1.size()<<" "<<gde2.size()<<" "<<gde3.size()<<endl;

        bool ok=true;
        g[p][0]=++idx;
        g[p][1]=++idx;
        g[p][2]=++idx;
        if (!generate_tree(g[p][0],gde1,d+1)) ok=false;
        if (!generate_tree(g[p][1],gde2,d+1)) ok=false;
        if (!generate_tree(g[p][2],gde3,d+1)) ok=false;
        if (ok) return true;
    }

    return false;
}

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

    assert(generate_tree(1,perms,0));
}

int ans[6];
void dfs(int p)
{
    if (stapitam[p].size()==6)
    {
        ff(i,0,6) ans[i]=stapitam[p][i];
        answer(ans);
    }
    else if (stapitam[p].front()==1)
    {
        int x=getLightest(stapitam[p][1],stapitam[p][2],stapitam[p][3]);
        if (x==stapitam[p][1]) dfs(g[p][0]);
        if (x==stapitam[p][2]) dfs(g[p][1]);
        if (x==stapitam[p][3]) dfs(g[p][2]);
    }
    else if (stapitam[p].front()==2)
    {
        int x=getMedian(stapitam[p][1],stapitam[p][2],stapitam[p][3]);
        if (x==stapitam[p][1]) dfs(g[p][0]);
        if (x==stapitam[p][2]) dfs(g[p][1]);
        if (x==stapitam[p][3]) dfs(g[p][2]);
    }
    else if (stapitam[p].front()==3)
    {
        int x=getHeaviest(stapitam[p][1],stapitam[p][2],stapitam[p][3]);
        if (x==stapitam[p][1]) dfs(g[p][0]);
        if (x==stapitam[p][2]) dfs(g[p][1]);
        if (x==stapitam[p][3]) dfs(g[p][2]);
    }
    else
    {
        int x=getNextLightest(stapitam[p][1],stapitam[p][2],stapitam[p][3],stapitam[p][4]);
        if (x==stapitam[p][1]) dfs(g[p][0]);
        if (x==stapitam[p][2]) dfs(g[p][1]);
        if (x==stapitam[p][3]) dfs(g[p][2]);
    }
}

void orderCoins()
{
    dfs(1);
}

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'int evalwtf(int, int, int, int)':
scales.cpp:97:13: warning: unused variable 'red' [-Wunused-variable]
   97 |         int red=0; bool svrsio=0; bool oki=false;
      |             ^~~
scales.cpp: In function 'bool generate_tree(int, std::vector<std::vector<int> >, int)':
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:134:5: note: in expansion of macro 'fff'
  134 |     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:134:16: note: in expansion of macro 'fff'
  134 |     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:134:29: note: in expansion of macro 'fff'
  134 |     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:138:9: note: in expansion of macro 'fff'
  138 |         fff(_,1,6) if (_!=i && _!=j && _!=k)
      |         ^~~
scales.cpp:163:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |         if (upito>sperms.size()/80+5) return false;
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
scales.cpp:172:23: warning: declaration of 'auto p' shadows a parameter [-Wshadow]
  172 |             for (auto p : sperms)
      |                       ^
scales.cpp:119:24: note: shadowed declaration is here
  119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
      |                    ~~~~^
scales.cpp:185:23: warning: declaration of 'auto p' shadows a parameter [-Wshadow]
  185 |             for (auto p : sperms)
      |                       ^
scales.cpp:119:24: note: shadowed declaration is here
  119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
      |                    ~~~~^
scales.cpp:199:23: warning: declaration of 'auto p' shadows a parameter [-Wshadow]
  199 |             for (auto p : sperms)
      |                       ^
scales.cpp:119:24: note: shadowed declaration is here
  119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
      |                    ~~~~^
scales.cpp:212:41: warning: declaration of 'int d' shadows a parameter [-Wshadow]
  212 |             int a=qq[1],b=qq[2],c=qq[3],d=qq[4];
      |                                         ^
scales.cpp:119:59: note: shadowed declaration is here
  119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
      |                                                       ~~~~^
scales.cpp:213:23: warning: declaration of 'auto p' shadows a parameter [-Wshadow]
  213 |             for (auto p : sperms)
      |                       ^
scales.cpp:119:24: note: shadowed declaration is here
  119 | bool generate_tree(int p, vector<vector<int>> sperms, int d)
      |                    ~~~~^
scales.cpp:215:21: warning: unused variable 'red' [-Wunused-variable]
  215 |                 int red=0; bool svrsio=0; bool oki=false;
      |                     ^~~
scales.cpp: In function 'void init(int)':
scales.cpp:247:15: warning: unused parameter 'T' [-Wunused-parameter]
  247 | void init(int T)
      |           ~~~~^
scales.cpp: In function 'void dfs(int)':
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:263:9: note: in expansion of macro 'ff'
  263 |         ff(i,0,6) ans[i]=stapitam[p][i];
      |         ^~

Subtask 1100 / 100

#Verdict Execution timeMemoryGrader output
Fetching results...