Submission #685144

#	Time	Username	Problem	Language	Result	Execution time	Memory
685144		guagua0407	Genetics (BOI18_genetics)	C++17	100 / 100	918 ms	33492 KiB

genetics

/*
燒雞
 燒雞
  燒雞    好想進選訓
 燒雞
燒雞
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end() 
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=4105;
const ll r=5;
const ll MOD=(1LL<<61)-1;
ll powv[mxn];
ll cnt[mxn][4];
char dna[mxn][mxn];
map<char,int> mp;

int main() {_
    //setIO("wayne");
    //對於第i排賦值R^i
    //最後答案要為(1+R+R^2+...+R^(n-1))*k
    //碰撞機遇怎麼算啦幹？？？
    mp['A']=0;
    mp['C']=1;
    mp['G']=2;
    mp['T']=3;
    int n,m,k;
    cin>>n>>m>>k;
    powv[0]=1;
    for(int i=1;i<n;i++){
        powv[i]=((__int128)powv[i-1]*r)%MOD;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            char c;
            cin>>c;
            dna[i][j]=c;
            cnt[j][mp[c]]=(cnt[j][mp[c]]+powv[i])%MOD;
        }
    }
    ll target=0;
    for(int i=0;i<n;i++){
        target=(target+((__int128)k*powv[i])%MOD)%MOD;
    }
    for(int i=0;i<n;i++){
        ll ans=0;
        for(int j=0;j<m;j++){
            for(int k=0;k<4;k++){
                if(k==mp[dna[i][j]]) continue;
                ans=(ans+cnt[j][k])%MOD;
            }
        }
        ll tmp=(target-((__int128)k*powv[i])%MOD)%MOD;
        tmp=(tmp+MOD)%MOD;
        if(ans==tmp){
            cout<<i+1;
            return 0;
        }
    }
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

genetics.cpp: In function 'void setIO(std::string)':
genetics.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 27 / 27
• Subtask 2: 19 / 19
• Subtask 3: 28 / 28
• Subtask 4: 26 / 26