Submission #203738

#	Time	Username	Problem	Language	Result	Execution time	Memory
203738		thebes	Fishing Game (RMI19_fishing)	C++14	100 / 100	1792 ms	42616 KiB

fishing

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm,tune=native")
#include <bits/stdc++.h>
#define DEBUG 1
using namespace std;

namespace output{
    void __(short x){cout<<x;}
    void __(unsigned x){cout<<x;}
    void __(int x){cout<<x;}
    void __(long long x){cout<<x;}
    void __(unsigned long long x){cout<<x;}
    void __(double x){cout<<x;}
    void __(long double x){cout<<x;}
    void __(char x){cout<<x;}
    void __(const char*x){cout<<x;}
    void __(const string&x){cout<<x;}
    void __(bool x){cout<<(x?"true":"false");}
    template<class S,class T>
    void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");}
    template<class T>
    void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class T>
    void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    template<class S,class T>
    void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");}
    void pr(){cout<<"\n";}
    template<class S,class... T>
    void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);}
}

using namespace output;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
typedef pair<ld,ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;

#define pb push_back
#define fox(i,x,y) for(int i=(x);i<=(y);i++)
#define foxr(i,x,y) for(int i=(y);i>=(x);i--)

const int MN = 305, mod = 1e9+7;
int dp[MN][MN][MN], N, T, i, j, x, y, w, f, cc[3];
vi pos[MN];
inline void add(int &x,int y){x+=y; if(x>=mod) x-=mod;}

int main(){
    for(scanf("%d%d",&N,&T);T;T--){
        for(i=1;i<=3*N;i++) pos[i].clear();
        for(j=1;j<=3;j++){
            for(i=1;i<=2*N;i++){
                scanf("%d",&x);
                pos[x].pb(j);
            }
        }
        int a=0, b=0, c=0;
        for(i=1;i<=3*N;i++){
            if(pos[i][0]==pos[i][1]) continue;
            pii p(pos[i][0],pos[i][1]);
            if(p.first>p.second) swap(p.first,p.second);
            if(p==make_pair(2,3)) a++;
            else if(p==make_pair(1,3)) b++;
            else c++;
        }
        dp[0][0][0]=1;
        int tt;
        if(N>=90) tt = ceil(1.0/3.0*(a+b+c));
        else tt = a+b+c;
        for(int s=1;s<=a+b+c;s++){
            for(i=0;i<=min(s,a+tt);i++){
                for(j=0;j<=min(s,b+tt);j++){
                    int k = s-i-j;
                    if(k<0||k>min(s,c+tt)) continue;
                    dp[i][j][k] = 0;
                    for(int ii=0;ii<3;ii++){
                        if(ii==2&&j+k) continue;
                        for(int jj=0;jj<3;jj++){
                            for(int kk=0;kk<3;kk++){
                                cc[0]=k,cc[1]=i,cc[2]=j; f=1;
                                if(ii!=2){
                                    if(ii==0&&cc[0]>0) f=1LL*f*cc[0]%mod,cc[0]--;
                                    else if(ii==1&&cc[2]>0) f=1LL*f*cc[2]%mod, cc[2]--,cc[1]++;
                                    else continue;
                                }
                                if(jj!=2||cc[0]+cc[1]>0){
                                    if(jj==0&&cc[1]>0) f=1LL*f*cc[1]%mod,cc[1]--;
                                    else if(jj==1&&cc[0]>0) f=1LL*f*cc[0]%mod,cc[0]--,cc[2]++;
                                    else continue;
                                }
                                if(kk!=2||cc[1]+cc[2]>0){
                                    if(kk==0&&cc[2]>0) f=1LL*f*cc[2]%mod,cc[2]--;
                                    else if(kk==1&&cc[1]>0) f=1LL*f*cc[1]%mod,cc[1]--,cc[0]++;
                                    else continue;
                                }
                                if(cc[0]+cc[1]+cc[2]<i+j+k) dp[i][j][k]=(dp[i][j][k]+1LL*f*dp[cc[1]][cc[2]][cc[0]])%mod;
                            }
                        }
                    }
                }
            }
        }
        printf("%d\n",dp[a][b][c]);
    }
    return 0;
}

Compilation message (stderr)

fishing.cpp: In function 'int main()':
fishing.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(scanf("%d%d",&N,&T);T;T--){
         ~~~~~^~~~~~~~~~~~~~
fishing.cpp:60:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d",&x);
                 ~~~~~^~~~~~~~~

• Subtask 1: 100 / 100