답안 #239656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239656	2020-06-17T05:31:53 Z	tduong0806	저울 (IOI15_scales)	C++14	100 / 100	73 ms	2816 KB

scales

#include<bits/stdc++.h>
#include "scales.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int hmt() {int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';if(n) x=-x;return x;}
#define in hmt()
#define ins ({string x;char c=getchar();for(;c==' '||c=='\n';c=getchar());for(;c!=' '&&c!='\n';c=getchar()) x+=c;x;})
#define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
#define fordec(i,a,b) for(int i=a;i>=b;--i)
#define forb(i,BS) for(int i=BS._Find_first();i< BS.size();i = BS._Find_next(i))
#define timer 1.0*clock()/CLOCKS_PER_SEC
#define forv(a,b) for(auto &a:b)
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define onbit(x,i) (x|(1<<(i-1)))
#define offbit(x,i) (x&~(1<<(i-1)))
const int N=7,M=800;
int a[N],p[M][N],kt[M][M],res;
struct oo
{
    int it,A,B,C,D,E;
} q[M];
/*map<vector<int>,int> f;
int F(vector<int> a,int l)
{
    if(a.size()==1) return 0;
    if(l>=6) return 10;
    if(f[a]) return f[a];
    int ret=10;
    forinc(i,1,360) if(i%3==1)
    {
        int mx=-1;
        forinc(j,0,2)
        {
            vector<int> b;
            forv(e,a) if(kt[e][i+j]) b.pb(e);
            if(b.size()&&b.size()<a.size()) mx=max(mx,F(b,l+1));
        }
        if(mx!=-1) ret=min(ret,mx+1);
        if(ret+l==6) break;
    }
    //cout<<a.size()<<" "<<ret<<"\n";
    /*cout<<"test\n";
    cout<<a.size()<<"\n";
    forv(x,a) {cout<<x<<" ";cout<<"\n";}
    cout<<ret<<"\n";exit(0);
    return f[a]=ret;
}*/
void init(int T)
{
    forinc(i,1,6) a[i]=i;
    int cnt=0;
    do
    {
        ++cnt;
        forinc(i,1,6) p[cnt][a[i]]=i;
    }
    while(next_permutation(a+1,a+7));
    cnt=0;
    forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
    {
        forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={1,A,B,C,0,i};
        forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={2,A,B,C,0,i};
        forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={3,A,B,C,0,i};
    }
    forinc(D,1,6) forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
    if(A!=D&&B!=D&&C!=D) forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={4,A,B,C,D,i};
    forinc(i,1,720) forinc(j,1,360)
    {
        int it=q[j].it,A=q[j].A,B=q[j].B,C=q[j].C,D=q[j].D,E=q[j].E;
        int ma=max({p[i][A],p[i][B],p[i][C]});
        int mi=min({p[i][A],p[i][B],p[i][C]});
        if(it==1) kt[i][j]=(p[i][E]>=ma);
        else if(it==2) kt[i][j]=(p[i][E]<=mi);
        else if(it==3) kt[i][j]=(p[i][E]>mi&&p[i][E]<ma);
        else if(it==4)
        {
            if(p[i][D]>ma) kt[i][j]=(p[i][E]<=mi);
            else
            {
                bool ok=1;
                if(p[i][D]>p[i][E]) ok=0;
                else
                {
                    if(p[i][A]>p[i][D]&&p[i][A]<p[i][E]) ok=0;
                    if(p[i][B]>p[i][D]&&p[i][B]<p[i][E]) ok=0;
                    if(p[i][C]>p[i][D]&&p[i][C]<p[i][E]) ok=0;
                }
                kt[i][j]=ok;
            }
        }
    }
}
/*int getHeaviest(int A,int B,int C)
{
    cout<<"getHeaviest"<<" "<<A<<" "<<B<<" "<<C<<"\n";
    int x;cin>>x;
    return x;
}
int getMedian(int A,int B,int C)
{
    cout<<"getMedian"<<" "<<A<<" "<<B<<" "<<C<<"\n";
    int x;cin>>x;
    return x;
}
int getLightest(int A,int B,int C)
{
    cout<<"getLightest"<<" "<<A<<" "<<B<<" "<<C<<"\n";
    int x;cin>>x;
    return x;
}
int getNextLightest(int A,int B,int C,int D)
{
    cout<<"getNextLightest"<<" "<<A<<" "<<B<<" "<<C<<" "<<D<<"\n";
    int x;cin>>x;
    return x;
}
void answer(int a[])
{
    cout<<"answer\n";
    forinc(i,0,5) cout<<a[i]<<" ";
}*/
void orderCoins()
{
    vector<int> a;
    forinc(i,1,720) a.pb(i);
    while(a.size()>1)
    {
        int ret=1000,j;
        forinc(i,1,360) if(i%3==1)
        {
            int mx=-1;
            forinc(j,0,2)
            {
                vector<int> b;
                forv(e,a) if(kt[e][i+j]) b.pb(e);
                if(b.size()&&b.size()<a.size()) mx=max(mx,int(b.size()));
            }
            if(mx!=-1&&ret>=mx+1) ret=mx+1,j=i;
        }
        int it=q[j].it,A=q[j].A,B=q[j].B,C=q[j].C,D=q[j].D,E;
        if(it==1) E=getHeaviest(A,B,C);
        else if(it==2) E=getLightest(A,B,C);
        else if(it==3) E=getMedian(A,B,C);
        else if(it==4) E=getNextLightest(A,B,C,D);
        forinc(i,1,360) if(i==j)
        {
            forinc(j,0,2) if(q[i+j].E==E)
            {
                vector<int> b;
                forv(e,a) if(kt[e][i+j]) b.pb(e);
                a=b;
            }
        }
    }
    int ans[6];
    forinc(i,1,6) ans[p[a[0]][i]-1]=i;
    answer(ans);
}
/*int main()
{
    init(0);
    orderCoins();
}*/

Compilation message

scales.cpp:49:5: warning: "/*" within comment [-Wcomment]
     /*cout<<"test\n";
      
scales.cpp: In function 'void init(int)':
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:66:19: note: in expansion of macro 'forinc'
     forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                   ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:66:5: note: in expansion of macro 'forinc'
     forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
     ^~~~~~
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:66:35: note: in expansion of macro 'forinc'
     forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                                   ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:66:19: note: in expansion of macro 'forinc'
     forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                   ^~~~~~
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:68:9: note: in expansion of macro 'forinc'
         forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={1,A,B,C,0,i};
         ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:66:35: note: in expansion of macro 'forinc'
     forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                                   ^~~~~~
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:69:9: note: in expansion of macro 'forinc'
         forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={2,A,B,C,0,i};
         ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:66:35: note: in expansion of macro 'forinc'
     forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                                   ^~~~~~
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:70:9: note: in expansion of macro 'forinc'
         forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={3,A,B,C,0,i};
         ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:66:35: note: in expansion of macro 'forinc'
     forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                                   ^~~~~~
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:72:19: note: in expansion of macro 'forinc'
     forinc(D,1,6) forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                   ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:72:5: note: in expansion of macro 'forinc'
     forinc(D,1,6) forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
     ^~~~~~
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:72:33: note: in expansion of macro 'forinc'
     forinc(D,1,6) forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                                 ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:72:19: note: in expansion of macro 'forinc'
     forinc(D,1,6) forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                   ^~~~~~
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:72:49: note: in expansion of macro 'forinc'
     forinc(D,1,6) forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                                                 ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:72:33: note: in expansion of macro 'forinc'
     forinc(D,1,6) forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                                 ^~~~~~
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:73:26: note: in expansion of macro 'forinc'
     if(A!=D&&B!=D&&C!=D) forinc(i,1,6) if(A==i||B==i||C==i) q[++cnt]={4,A,B,C,D,i};
                          ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:72:49: note: in expansion of macro 'forinc'
     forinc(D,1,6) forinc(A,1,6) forinc(B,A+1,6) forinc(C,B+1,6)
                                                 ^~~~~~
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:74:21: note: in expansion of macro 'forinc'
     forinc(i,1,720) forinc(j,1,360)
                     ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:74:5: note: in expansion of macro 'forinc'
     forinc(i,1,720) forinc(j,1,360)
     ^~~~~~
scales.cpp:55:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T)
               ^
scales.cpp: In function 'void orderCoins()':
scales.cpp:131:17: warning: declaration of 'a' shadows a global declaration [-Wshadow]
     vector<int> a;
                 ^
scales.cpp:24:5: note: shadowed declaration is here
 int a[N],p[M][N],kt[M][M],res;
     ^
scales.cpp:139:20: warning: declaration of 'j' shadows a previous local [-Wshadow]
             forinc(j,0,2)
                    ^
scales.cpp:9:31: note: in definition of macro 'forinc'
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                               ^
scales.cpp:135:22: note: shadowed declaration is here
         int ret=1000,j;
                      ^
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:139:13: note: in expansion of macro 'forinc'
             forinc(j,0,2)
             ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:136:9: note: in expansion of macro 'forinc'
         forinc(i,1,360) if(i%3==1)
         ^~~~~~
scales.cpp:154:20: warning: declaration of 'j' shadows a previous local [-Wshadow]
             forinc(j,0,2) if(q[i+j].E==E)
                    ^
scales.cpp:9:31: note: in definition of macro 'forinc'
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                               ^
scales.cpp:135:22: note: shadowed declaration is here
         int ret=1000,j;
                      ^
scales.cpp:9:35: warning: declaration of '_b' shadows a previous local [-Wshadow]
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:154:13: note: in expansion of macro 'forinc'
             forinc(j,0,2) if(q[i+j].E==E)
             ^~~~~~
scales.cpp:9:35: note: shadowed declaration is here
 #define forinc(i,a,b) for(int i=a,_b=b;i<=_b;++i)
                                   ^
scales.cpp:152:9: note: in expansion of macro 'forinc'
         forinc(i,1,360) if(i==j)
         ^~~~~~
scales.cpp:154:27: warning: 'E' may be used uninitialized in this function [-Wmaybe-uninitialized]
             forinc(j,0,2) if(q[i+j].E==E)
                           ^~
scales.cpp:147:51: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int it=q[j].it,A=q[j].A,B=q[j].B,C=q[j].C,D=q[j].D,E;
                                                   ^

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	2560 KB	Output is correct
2	Correct	51 ms	2560 KB	Output is correct
3	Correct	54 ms	2560 KB	Output is correct
4	Correct	49 ms	2688 KB	Output is correct
5	Correct	73 ms	2560 KB	Output is correct
6	Correct	58 ms	2560 KB	Output is correct
7	Correct	50 ms	2592 KB	Output is correct
8	Correct	52 ms	2688 KB	Output is correct
9	Correct	49 ms	2688 KB	Output is correct
10	Correct	50 ms	2688 KB	Output is correct
11	Correct	54 ms	2560 KB	Output is correct
12	Correct	53 ms	2560 KB	Output is correct
13	Correct	52 ms	2688 KB	Output is correct
14	Correct	51 ms	2560 KB	Output is correct
15	Correct	49 ms	2560 KB	Output is correct
16	Correct	50 ms	2680 KB	Output is correct
17	Correct	49 ms	2560 KB	Output is correct
18	Correct	50 ms	2560 KB	Output is correct
19	Correct	49 ms	2560 KB	Output is correct
20	Correct	50 ms	2560 KB	Output is correct
21	Correct	49 ms	2560 KB	Output is correct
22	Correct	50 ms	2688 KB	Output is correct
23	Correct	54 ms	2560 KB	Output is correct
24	Correct	50 ms	2680 KB	Output is correct
25	Correct	48 ms	2560 KB	Output is correct
26	Correct	49 ms	2560 KB	Output is correct
27	Correct	49 ms	2560 KB	Output is correct
28	Correct	50 ms	2656 KB	Output is correct
29	Correct	51 ms	2560 KB	Output is correct
30	Correct	50 ms	2816 KB	Output is correct
31	Correct	48 ms	2688 KB	Output is correct
32	Correct	49 ms	2560 KB	Output is correct
33	Correct	49 ms	2688 KB	Output is correct
34	Correct	50 ms	2688 KB	Output is correct
35	Correct	49 ms	2688 KB	Output is correct
36	Correct	49 ms	2560 KB	Output is correct
37	Correct	48 ms	2560 KB	Output is correct
38	Correct	52 ms	2688 KB	Output is correct
39	Correct	60 ms	2688 KB	Output is correct
40	Correct	51 ms	2560 KB	Output is correct