Submission #1267979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267979		shiori_chan	Genetics (BOI18_genetics)	C++17	46 / 100	2092 ms	3948 KiB

genetics

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <bitset>
#define all(x) x.begin(), x.end()
#define pb push_back
#define fi first
#define se second
#define compact(v) v.erase(unique(all(v)) , v.end())
#define pi pair<int , int>
#define vi vector<int>
#define eb emplace_back
#define FOR(i , l , r) for(int i = l; i <= r; ++ i)
#define FORD(i , l , r) for(int i = l; i >= r; -- i)

using namespace std;
typedef long long ll;

const int nd = 4101;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);

bitset<4100> g[4][nd];
int n , m , k;

bool ok(int s){
	FOR(i , 1 , n) if(i != s){
		int cnt = 0;
		FOR(t , 0 , 3) cnt += (g[t][i] ^ g[t][s]).count();
		cnt /= 2; 
		if(cnt != k) return false;
	}
	return true;
}

void solve(){
	cin >> n >> m >> k;

	FOR(i , 1 , n){
		FOR(j , 0 , m - 1){
			char d;
			cin >> d;
			
			if(d == 'A') g[0][i][j] = true;
			if(d == 'C') g[1][i][j] = true;
			if(d == 'G') g[2][i][j] = true;
			if(d == 'T') g[3][i][j] = true;
 		}
	}

	FOR(i , 1 , n){
		if(ok(i)){
			cout << i;
			return;
		}
	}
}

signed main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);

	#define task "panh" 
	if(fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	solve();

	return 0;
}
/*
			   -.                                                                             ::.            -:       .:::::::::: 
 ***##*###**##@%***+###+***+**++******#*******#*******++*****+*+=@*+####%@@@@@%*===#*%@===---**#@@#=*######***@@@#*###=*@%#######:
 **##*##*+*%#%@**+**##****************#***+***#*+*+***+++******+=@#+*#=:--===-====-*#+@%:#@@%##*#%%#+########+*@%%@#*##+=@%######:
 #%####*+*%##@#+*+*###**#********##***#++***++#********#***+++++=%@=###==========:#:#+*@######*%##%%#=+###*##*+#@##@%###+=%%#####:
 #####***%##@%+***#%#++#######*********++***#*#+##%%%##****#####+#@ ###===++++=-=@@#**+#%+*+##+#%##%%#+*######*+%%###@###*=#%####:
 ##*****####@*+***###+=**#+==*+*###%#%%###%%**%*#=::-+#%####+#=-#+@=-###===+==-#@#*###+=@#+*+##*#%##%##=*######*+@%###%%*#*+%%###:
 %##***####@#++*+#%+*++=+++=+#**#===-==+*+=:=+@-#+-===-:+#%+:+#:#=@@.#%#----:-###*****#=*@+++***+#%#%#%#+*###*##**@####%@#***%###:
 *####*@##%@++***##+###+====##+##==========-+*@:%+-=-::::::::=@:#=@%+=##**==#@#####*###+=@%=****#+%##@#%#=####*##+#%#####%##**%##:
 #**#*#%##@#*#***##**########*+#*-=*+==+===-++@.%=::+@#+=:.=@*#=#=@%#=*@*####**+*********+@*=+*****%#%%*%+*####****@######%%**#%#:
 ####*####@++*+*#%+*#**********##*####-====:*=@.#-:####%%@@%#####=%%#=+@#=+***++*******+#=%@+++*++=*%#@###=*######+@%######@#+###.
 ###**%##@#*****#@*##*#**#***+*******##*==##*=@=%#%%##*##*##+*##*-%@%==#@+=*+******#****##+@%+=+***+##%%*##*#**##**+@#######@**##:
 ###*#%##@++#*+*##*##****##****#*******####*+=@=%+********#*=*##*-#@#*:*@#=+***+**+++***=@=@@@#=++++=@#@#+%***#####+@#######%#+##.
 ###*#%#%%**##+*%#**#*#**#***********#******+=@=%=*++**#**#*+**++-#@*@-=@#=+***+++*+****=#*@ @@#=*##+*#@%++#**#####*%%#######@+##:
 ###*###@#**##+*@*************#************#==@+@=+*+++***#+++*++=@@*##:%@#=++++++++++**+*%@@ @@%-=+++##@#=%+*#*#***#%#######%##%:
 ##*#%##@***##+#%**#***#***#********+***#+*#==@#@:=+++++**@=+++++*#@@*%-+@@==++**+**++**++%@@  @@@=-=+##@%=##+#*#***#%###########.
 ##*#%##@*#*##=*%**#*******+***********+*+*+=-@#@-=++++=+%*=+***+@. @###:@%%=******+*****=#@@    @@@*:-#@%+=%+#*###+#@###########:
:@#*#%##%#**##+#%+************#*****++***+#*+-%%@==+++*=+@=++++==@  @@#%=##%==+*++*+*****=#@@     @@@@#*#@*-@+***##+#%########%%#:
 #@*##%@#*###*+#%*##****+***++***++**+++++++*-%@@*=++++=%%-==**#@@@@@@##%+#%%-=+++++**+**==@@        @#*+@*=##***##+*@###########:
  @*%%#%##*##**#%**####*#***********++**+**+*-#@%#-+++=:@=#%##+#@    @@#####@#=++**+******-@=  *@@@@@@@@@@@=+#****#*+@###########:
 @@@%##@#**##*+#%**************+*****+++++++*=#@#@:=+==@@-====*@     @@######@+=+++++++*++=@  @@@@@@@@  +@@=+#****#*=%%##########:
  #@@%#@##*###+#@***********+*#*++++++***+*+#=*@#%++=:@@==+*++@@  ..  @@#####%@-=***+*****=@@@@@@   .@@.@ @#=***#+#*=@@##########:
	@%#@#*##**+#@#**#*******+*#++****++++*++#=+@##@ :@@*-+==+@@   .:   @@#####@@=+++++*++**=@@%@@@   -@@@:*@=*#**+#*+@*@#########:
 =:  ##@**####+#@***********+*#++***+++++*++#+=@##@%@@#:=++*@@     ..  #@@#####@#=+**+*+#@@%#@##@@   @  @-=@=****+%*=@-#@%#######:
 : :@@*@##****+#@*+****#****+*%+*****+++++++#==@###%@@-=*+*@@   -*+     =@@#####@*=+**++#= -@%   :  @% -@==@=#***+@*=@% +@@######:
  @@@*+@##**+*+#@#+*******+*++@=+***++**++++**=@##@@*-=+==*.        *::  -@@*####%#-++++##=:%   @-@@%  *@=-@=#***+@+=%@@. @@@%###:
+@@#*+*@##*###=#@#=****#****++@*=*+*++++++++*+=@@@%-:==--+@@@@@@@@#        @@####%%*-=+++#+=@@ :       +@+=@+#**++@+=@#%@%- -##%%:
 ##%#*#@##**##=#@%+*********+=%#=*++++++*++====@@::-=+##@@@@@@@@@@@@@@      @@@*##%##===++**#@      .. :@*-@%***+*@==@###%@@%####:
 ###%@%@##****=#@@++*#*******=#@=++++*+*+===#@%-:-##+=#@#===@      ::++      =@@***#*#=-==++=@@         @#=#@*+*=#%==@@%#*###%@##.
 #*@ @@@#**###=#@%*+*********+=@+=***+-==#@@+---=+++#@@@@@@@@@                 @@@*+%##*--=+==@+   .    @@+#@*=+=@#==@###%%%#####.
 **@  @@%****#+#@@#+*********+-@#:====@@#==-===++#@@@@@  @  @@                   @@@+*#+**:-==*@     .  @@**@+=+*%#=+@###########.
 ++@: @@%+*#**++@%@=**+++++===-%@@@@@#=-==+=--+#@@@    @@       . .                @@@@#=+**=--#@       +@**@+==##*-#@###########:
-@@@   @#-======%%@*===*###@@@@#=----==+==-=#@@@@ @@*      :@=                        @@@@@#*#=:#@       @*#@==+%#+*#@%##########:
 %@@@@@@#%@@@@@@@%@@@@@%##+=---=+=====-=+@@@#=#*@   ::.+@#:                              :#@@@@#+#@@     @#@@--%%#=#*%###########:
%@@  @%@#%##++======------=========#%@@@@=====*=@#%@@%-                             ...       @@@@@@@@#  @*@#:=@#**#*@###########.
   @@%-@*=*#@@@@%#*+*#%@@@@@@@@@@@@@+=--=+***+##@                                  .        .       .*%  @@@:-@##=#+#@#%#########.
 @@@**=@++++=:=%%##@@@##%%%##*+==@%==++******+*#@                                 ..     .  #            @@*:##**##+#%##########%.
+@@#***@+***++@####@*@#=-==+++*+=%@@=+*******++#@=                                 .   ..  =.           @@@.:@*#*##+@%########### 
:%#**#%@=**+=%%###@@+@#%++******=*@@#=********+%@@                                         .            @@.:@**###*+@###*%#######.
:#+*##@%+**=%%###*@+##@#%*=*#***+=@%@++******+++@@                                                     @@:.@@=#**#=@@############.
 ++##%@*++=#@###*%@*##@##%#=+****=#%%#=**+*****+%@                                                    @@.=@@@=*##*=@######%###### 
 #%%@@@++=%@#####@#####@*##%+++**+*@%@*=+******+=@+                                          .       @@.#%#@%=###=#%#%####%###### 
:@@@-@#==@@####*@*#%####@*##%*=+*+=#@#@*=++****+=%@                                        @        %@@@##@@++##=-@###%########## 
 +-=@@=+@%####*%%%%%%###%@*##%%==+=#%#%%+=+*****==@                                  :=-::         @@@@*#%#@=*#+-@########=@##### 
 **%@#*%%####*#@%@*%%#%##@#*##%@*==+%###@*=+*++*+-@@                           :::                @@%%#@###%+#=.@%########+%##### 
 #@@########*@@@@%:@%%%###@%####%@+:##@##%*=+*+++==@                                            :@@%%@####@**-:@%######%*#*###### 
 @%#######**@@#@+=-@%######@######@#=##%##@%==+++==@@                                      @@  =@@%######@@+ =@%################# 
=%#######+@@##@#+*=@##%%####@%##############@=======@                                     @%@-@@@#######@%: @@##########%#*###### 
.######*%@@%#%@+**=@#######@.@%##########%**#%#=====*@  :.                                **@@:@@@#####@# +@%#############*###### 
.#%##+@@@%=#%@#*#**@#%%####@:=%@##%##*######*##@*=-==#@   :=@@:                           @ -##-@@@###%-=@%############*##+%##### 
:#=*@@#*=+=%%#**#+#@#@#####@-==%@**#%#*****##**##%*:--#@       :+%@@@*                     :      @@@#*###################+%##### 
 @@###+*#*#@%##*#+%%%@*%###@=++=%@#*#%%#*+********##*-:=@+             @@@@#:             +@       *@@@#############**######*#### 
 #####***+@@**##**%@@-#%###@=***-%@%***@%#++***#++**###-=%@           @   .-+#%@@@@@@@@@@@@@@        #@@@%#############*#*#####** 
 ####%*#*#@#**##*#%@::@%###@=#+#=-##@*+*#@@#*=++##=+**##*=*@%       @@  :::::::.  #@  @@%###@@          @@@@#########**##******** 
.#####**#@#*####+#@@ #@##%@@=#=%=+=#*@@@@%+%@@@@%*#@===+**+#%@@    @%:.::::::--:: @@ =@*#=#*@@@@          +@@@#*#*******###*###** 
 #####**%#**##***@@= @%##@:#+%=@++=#*@* @@@@#*  @@@@#@@+=+****@@@+ :              @@ +@#=:%#@ @@@%           @@@%#######**#**+*** 
.####**%%**###**%@@  @%#@@ #%#=##==#*@@    @@@@@    @@@@@@@+==+*#@@@@@=:    :#@@@ @@ =@#=-###@ #@@@@           @@@@#************* 
 ####*#%*#####+#@@  =@%%@ @+@#=+#==#*@* .     +@@@@        *@@@*=++==#@@@@@@@:    @@:-@#=-*##@= @@#@@@           #@@@#*********** 
.#######**###**@@=  @@@@+ ##@#=+#*=##@    ::.     :@@@@@@@-    :@*@@@@@@=       : -@@=#+==+##*@@: %==@@@@           @@@@#****++++ 
 ######*##*##*@@#  *@@@= @#@@#=++@+##@ +#=    @@@@#+-*%@@@@@@@@@%.       %@@@@@@%= @=@#+===##++=%@:@=:#@@@@           -@@@@%#**** 
 #####**##*+*#@%  =@%@@.*@@ @%+++=#*@@ .    @@@==@@@@@@-                         .@@@@@+===*+@=## @@@#-+%*@@@:            =@@@*++ 
 ####***#*+*#@@  :@#@@+ %#@ @@#+++*#@@ -. @@@##@@@#                                  @@@+====@.#@=  @@%==#**@@@-   :=:::.    @@*+ 
 ##*+*##*++@@@  #@#@@@  @#@  @@#++=*%@   *@%%@@@        .                              @@#===#=:@@@   @@@%@@@@@@@@=     .-:   #@* 
.##**#****%@@. @@*@@=  .@#@   @@@+=++@  @@%@@@      ......::                            #@@===@  @@@@ ::#@@=         .   .:-.  @@ 
 #+***++#%@@  @##@@    %@#@ *:  @@@+=*@@@@@@    ....     . ..::.                          @@+-*@  @@@.                ...   .   # 
 *#****##%% +@*#@%  .: @@#@      :@@@#@@@@     ...  ..         .:.                         @@#=#@  -                   .......    
 **++##### @##@@:  ::: =@#@  .:     @@@     ......... .  ..      ..                         @%#*@: # :            .=**=:.. ..:.   
 ++*####**#**@@   ::::  @@@@     @@@:    .:.......... ... . .     .:                        -@#+#@ : .:::..:=#%@@@@=    ......... 
 +######*+*@@*  :::::::   @@@@@@@@    ..:....... .....  .   ...   . .                        %+**%@  ..   #  -**       . . ..:... 
 ##**#*+=#@@:  ::::::::. .          :...:........... .  ..         ..                        ##-=#@  .   =@@=            . ...... 
 ####*+#@@*  :::-::::: ==-=: .::.:::..            ... .. ....       ...                      ##=-=@   :#+.          .::.  ...:::: 
																																  */

Compilation message (stderr)

genetics.cpp: In function 'int main()':
genetics.cpp:67:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:68:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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