oj.uz

답안 #887694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887694 2023-12-15T03:02:37 Z nnhzzz Genetics (BOI18_genetics) C++14
100 / 100
 1319 ms 85336 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
 
#include<bits/stdc++.h>

using namespace std;

#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i += c)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define MASK(x) (1LL<<(x))
#define BIT(x,i) (((x)>>(i))&1LL)
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define fi first
#define se second
#define gcd __gcd
#define ld long double
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define endl "\n"
//#define int ll

//-------------------------------------------------------------------------------------------------------//
int readInt(){
    char c;
    do{
        c = getchar();
    }while(c!='-' && !isdigit(c));
    bool neg = (c=='-');
    int res = neg?0:c-'0';
    while(isdigit(c=getchar())) res = (res<<3)+(res<<1)+(c-'0');
    return neg?-res:res;
}
//-------------------------------------------------------------------------------------------------------//
template<typename T> bool mini(T &a, const T &b){if(a>b){a=b;return true;}return false;}
template<typename T> bool maxi(T &a, const T &b){if(a<b){a=b;return true;}return false;}
//-------------------------------------------------------------------------------------------------------//
const int MAXN = 4e3+123;
const int MOD = 1e9+7;
const int INF = 1e9;
const int LOG = 16;
const ll LINF = 5e17;
const ld EPS = 1e-9;
const ld PI = acos(-1);
//-------------------------------------------------------------------------------------------------------//

int a[MAXN][MAXN];
int n,m,k;

namespace sub1{

    void solve(){
        REP(l,1,n){
            int ok = 1;
            REP(i,1,n){
                if(i==l) continue;
                int cnt = 0;
                REP(j,1,m) if(a[l][j]!=a[i][j]) ++cnt;
                if(cnt!=k){
                    ok = 0;
                    break;
                }
            }
            if(ok){
                cout << l;
                return ;
            }
        }
    }
}

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

namespace sub2{
    bitset<MAXN> f[MAXN];
    int idx[MAXN];

    void solve(){
        srand(time(0));
        REP(i,1,n) idx[i] = i;
        shuffle(idx+1,idx+n+1,rd);
        REP(i,1,n) REP(j,1,m) f[i][j] = a[i][j]-1;
        REP(l,1,n){
            int ok = 1;
            REP(i,1,n){
                if(i==idx[l]) continue;
                if((f[idx[l]]^f[i]).count()!=k){
                    ok = 0;
                    break;
                }
            }
            if(ok){
                cout << idx[l];
                return ;
            }
        }
    }
}

namespace sub4{
    ll s[MAXN][5],rnd[MAXN];
    ll tot = 0;

    void solve(){
        srand(time(0));
        REP(i,1,n){
            rnd[i] = rd();
            tot += rnd[i];
            REP(j,1,m) s[j][a[i][j]] += rnd[i];
        }
        REP(i,1,n){
            ll hsh = 0;
            REP(j,1,m) hsh += tot-s[j][a[i][j]];
            if(hsh==1LL*k*(tot-rnd[i])){
                cout << i;
                return ;
            }
        }
    }
}

void solve(){
    cin >> n >> m >> k;
    int s2 = 1;
    REP(i,1,n){
        REP(j,1,m){
            char ch; cin >> ch;
            if(ch=='A') a[i][j] = 1;
            if(ch=='C') a[i][j] = 2;
            if(ch=='G') a[i][j] = 3;
            if(ch=='T') a[i][j] = 4;
            if(a[i][j]>2) s2 = 0;
        }
    }
    // sub4::solve(); return ;
    if(n<=100){
        sub1::solve();
        return ;
    }
    if(s2){
        sub2::solve();
        return ;
    }
    sub4::solve();
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #define task "test"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    #define task1 "nothing"
    if(fopen(task1".inp","r")){
        freopen(task1".inp","r",stdin);
        freopen(task1".out","w",stdout);
    }
    int test = 1;
    while(test--){
        solve();
        cout << endl;
    }
    return 0;
}

Compilation message

genetics.cpp: In function 'void sub2::solve()':
genetics.cpp:95:44: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   95 |                 if((f[idx[l]]^f[i]).count()!=k){
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~^~~
genetics.cpp: In function 'int main()':
genetics.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen(task1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(task1".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2648 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 26960 KB Output is correct
2 Correct 82 ms 33272 KB Output is correct
3 Correct 153 ms 31220 KB Output is correct
4 Correct 46 ms 23012 KB Output is correct
5 Correct 155 ms 33260 KB Output is correct
6 Correct 146 ms 33104 KB Output is correct
7 Correct 33 ms 16600 KB Output is correct
8 Correct 39 ms 16732 KB Output is correct
9 Correct 75 ms 31220 KB Output is correct
10 Correct 190 ms 31216 KB Output is correct
11 Correct 75 ms 26960 KB Output is correct
12 Correct 102 ms 29008 KB Output is correct
13 Correct 70 ms 26964 KB Output is correct
14 Correct 61 ms 24916 KB Output is correct
15 Correct 119 ms 25044 KB Output is correct
16 Correct 74 ms 27096 KB Output is correct
17 Correct 96 ms 31060 KB Output is correct
18 Correct 206 ms 31220 KB Output is correct
19 Correct 107 ms 31224 KB Output is correct
20 Correct 180 ms 31220 KB Output is correct
21 Correct 109 ms 31204 KB Output is correct
22 Correct 182 ms 31216 KB Output is correct
23 Correct 191 ms 31220 KB Output is correct
24 Correct 79 ms 31220 KB Output is correct
25 Correct 76 ms 31220 KB Output is correct
26 Correct 158 ms 31220 KB Output is correct
27 Correct 140 ms 31220 KB Output is correct
28 Correct 87 ms 31220 KB Output is correct
29 Correct 90 ms 31196 KB Output is correct
30 Correct 57 ms 33244 KB Output is correct
31 Correct 59 ms 33276 KB Output is correct
32 Correct 86 ms 33108 KB Output is correct
33 Correct 1 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 26960 KB Output is correct
2 Correct 82 ms 33272 KB Output is correct
3 Correct 153 ms 31220 KB Output is correct
4 Correct 46 ms 23012 KB Output is correct
5 Correct 155 ms 33260 KB Output is correct
6 Correct 146 ms 33104 KB Output is correct
7 Correct 33 ms 16600 KB Output is correct
8 Correct 39 ms 16732 KB Output is correct
9 Correct 75 ms 31220 KB Output is correct
10 Correct 190 ms 31216 KB Output is correct
11 Correct 75 ms 26960 KB Output is correct
12 Correct 102 ms 29008 KB Output is correct
13 Correct 70 ms 26964 KB Output is correct
14 Correct 61 ms 24916 KB Output is correct
15 Correct 119 ms 25044 KB Output is correct
16 Correct 74 ms 27096 KB Output is correct
17 Correct 96 ms 31060 KB Output is correct
18 Correct 206 ms 31220 KB Output is correct
19 Correct 107 ms 31224 KB Output is correct
20 Correct 180 ms 31220 KB Output is correct
21 Correct 109 ms 31204 KB Output is correct
22 Correct 182 ms 31216 KB Output is correct
23 Correct 191 ms 31220 KB Output is correct
24 Correct 79 ms 31220 KB Output is correct
25 Correct 76 ms 31220 KB Output is correct
26 Correct 158 ms 31220 KB Output is correct
27 Correct 140 ms 31220 KB Output is correct
28 Correct 87 ms 31220 KB Output is correct
29 Correct 90 ms 31196 KB Output is correct
30 Correct 57 ms 33244 KB Output is correct
31 Correct 59 ms 33276 KB Output is correct
32 Correct 86 ms 33108 KB Output is correct
33 Correct 1 ms 2396 KB Output is correct
34 Correct 1 ms 2396 KB Output is correct
35 Correct 1 ms 2396 KB Output is correct
36 Correct 571 ms 62004 KB Output is correct
37 Correct 710 ms 68816 KB Output is correct
38 Correct 1319 ms 68156 KB Output is correct
39 Correct 483 ms 59948 KB Output is correct
40 Correct 476 ms 68684 KB Output is correct
41 Correct 274 ms 37584 KB Output is correct
42 Correct 210 ms 37336 KB Output is correct
43 Correct 283 ms 59856 KB Output is correct
44 Correct 520 ms 68700 KB Output is correct
45 Correct 519 ms 68824 KB Output is correct
46 Correct 507 ms 68688 KB Output is correct
47 Correct 534 ms 61900 KB Output is correct
48 Correct 369 ms 61776 KB Output is correct
49 Correct 302 ms 53584 KB Output is correct
50 Correct 561 ms 53792 KB Output is correct
51 Correct 426 ms 59944 KB Output is correct
52 Correct 556 ms 68400 KB Output is correct
53 Correct 449 ms 68156 KB Output is correct
54 Correct 287 ms 68040 KB Output is correct
55 Correct 312 ms 67920 KB Output is correct
56 Correct 336 ms 67920 KB Output is correct
57 Correct 675 ms 68156 KB Output is correct
58 Correct 678 ms 67924 KB Output is correct
59 Correct 543 ms 68056 KB Output is correct
60 Correct 824 ms 67924 KB Output is correct
61 Correct 715 ms 68152 KB Output is correct
62 Correct 397 ms 68160 KB Output is correct
63 Correct 597 ms 68292 KB Output is correct
64 Correct 678 ms 68180 KB Output is correct
65 Correct 579 ms 68156 KB Output is correct
66 Correct 412 ms 68048 KB Output is correct
67 Correct 521 ms 68088 KB Output is correct
68 Correct 433 ms 67920 KB Output is correct
69 Correct 392 ms 67924 KB Output is correct
70 Correct 420 ms 68048 KB Output is correct
71 Correct 357 ms 68156 KB Output is correct
72 Correct 697 ms 68180 KB Output is correct
73 Correct 369 ms 67924 KB Output is correct
74 Correct 0 ms 2392 KB Output is correct
75 Correct 1 ms 2648 KB Output is correct
76 Correct 1 ms 2392 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 1 ms 2648 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 91 ms 26960 KB Output is correct
19 Correct 82 ms 33272 KB Output is correct
20 Correct 153 ms 31220 KB Output is correct
21 Correct 46 ms 23012 KB Output is correct
22 Correct 155 ms 33260 KB Output is correct
23 Correct 146 ms 33104 KB Output is correct
24 Correct 33 ms 16600 KB Output is correct
25 Correct 39 ms 16732 KB Output is correct
26 Correct 75 ms 31220 KB Output is correct
27 Correct 190 ms 31216 KB Output is correct
28 Correct 75 ms 26960 KB Output is correct
29 Correct 102 ms 29008 KB Output is correct
30 Correct 70 ms 26964 KB Output is correct
31 Correct 61 ms 24916 KB Output is correct
32 Correct 119 ms 25044 KB Output is correct
33 Correct 74 ms 27096 KB Output is correct
34 Correct 96 ms 31060 KB Output is correct
35 Correct 206 ms 31220 KB Output is correct
36 Correct 107 ms 31224 KB Output is correct
37 Correct 180 ms 31220 KB Output is correct
38 Correct 109 ms 31204 KB Output is correct
39 Correct 182 ms 31216 KB Output is correct
40 Correct 191 ms 31220 KB Output is correct
41 Correct 79 ms 31220 KB Output is correct
42 Correct 76 ms 31220 KB Output is correct
43 Correct 158 ms 31220 KB Output is correct
44 Correct 140 ms 31220 KB Output is correct
45 Correct 87 ms 31220 KB Output is correct
46 Correct 90 ms 31196 KB Output is correct
47 Correct 57 ms 33244 KB Output is correct
48 Correct 59 ms 33276 KB Output is correct
49 Correct 86 ms 33108 KB Output is correct
50 Correct 1 ms 2396 KB Output is correct
51 Correct 1 ms 2396 KB Output is correct
52 Correct 1 ms 2396 KB Output is correct
53 Correct 571 ms 62004 KB Output is correct
54 Correct 710 ms 68816 KB Output is correct
55 Correct 1319 ms 68156 KB Output is correct
56 Correct 483 ms 59948 KB Output is correct
57 Correct 476 ms 68684 KB Output is correct
58 Correct 274 ms 37584 KB Output is correct
59 Correct 210 ms 37336 KB Output is correct
60 Correct 283 ms 59856 KB Output is correct
61 Correct 520 ms 68700 KB Output is correct
62 Correct 519 ms 68824 KB Output is correct
63 Correct 507 ms 68688 KB Output is correct
64 Correct 534 ms 61900 KB Output is correct
65 Correct 369 ms 61776 KB Output is correct
66 Correct 302 ms 53584 KB Output is correct
67 Correct 561 ms 53792 KB Output is correct
68 Correct 426 ms 59944 KB Output is correct
69 Correct 556 ms 68400 KB Output is correct
70 Correct 449 ms 68156 KB Output is correct
71 Correct 287 ms 68040 KB Output is correct
72 Correct 312 ms 67920 KB Output is correct
73 Correct 336 ms 67920 KB Output is correct
74 Correct 675 ms 68156 KB Output is correct
75 Correct 678 ms 67924 KB Output is correct
76 Correct 543 ms 68056 KB Output is correct
77 Correct 824 ms 67924 KB Output is correct
78 Correct 715 ms 68152 KB Output is correct
79 Correct 397 ms 68160 KB Output is correct
80 Correct 597 ms 68292 KB Output is correct
81 Correct 678 ms 68180 KB Output is correct
82 Correct 579 ms 68156 KB Output is correct
83 Correct 412 ms 68048 KB Output is correct
84 Correct 521 ms 68088 KB Output is correct
85 Correct 433 ms 67920 KB Output is correct
86 Correct 392 ms 67924 KB Output is correct
87 Correct 420 ms 68048 KB Output is correct
88 Correct 357 ms 68156 KB Output is correct
89 Correct 697 ms 68180 KB Output is correct
90 Correct 369 ms 67924 KB Output is correct
91 Correct 0 ms 2392 KB Output is correct
92 Correct 1 ms 2648 KB Output is correct
93 Correct 1 ms 2392 KB Output is correct
94 Correct 330 ms 66256 KB Output is correct
95 Correct 314 ms 68812 KB Output is correct
96 Correct 359 ms 84284 KB Output is correct
97 Correct 196 ms 48196 KB Output is correct
98 Correct 128 ms 64080 KB Output is correct
99 Correct 744 ms 84932 KB Output is correct
100 Correct 184 ms 45632 KB Output is correct
101 Correct 179 ms 45648 KB Output is correct
102 Correct 257 ms 71760 KB Output is correct
103 Correct 425 ms 85044 KB Output is correct
104 Correct 366 ms 85336 KB Output is correct
105 Correct 365 ms 85072 KB Output is correct
106 Correct 347 ms 82516 KB Output is correct
107 Correct 684 ms 76372 KB Output is correct
108 Correct 283 ms 65872 KB Output is correct
109 Correct 311 ms 74064 KB Output is correct
110 Correct 306 ms 73820 KB Output is correct
111 Correct 332 ms 85180 KB Output is correct
112 Correct 361 ms 84720 KB Output is correct
113 Correct 307 ms 83796 KB Output is correct
114 Correct 292 ms 83796 KB Output is correct
115 Correct 346 ms 83784 KB Output is correct
116 Correct 358 ms 84524 KB Output is correct
117 Correct 360 ms 84564 KB Output is correct
118 Correct 355 ms 84432 KB Output is correct
119 Correct 353 ms 84276 KB Output is correct
120 Correct 388 ms 84528 KB Output is correct
121 Correct 724 ms 76172 KB Output is correct
122 Correct 365 ms 85064 KB Output is correct
123 Correct 509 ms 84200 KB Output is correct
124 Correct 1 ms 2396 KB Output is correct
125 Correct 1 ms 2396 KB Output is correct
126 Correct 1 ms 2392 KB Output is correct