oj.uz

답안 #736111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736111 2023-05-05T08:36:04 Z marvinthang Genetics (BOI18_genetics) C++17
100 / 100
 455 ms 83084 KB 
/*************************************
*    author: marvinthang             *
*    created: 05.05.2023 08:30:00    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
template <class T> T rand(T l, T h) { return uniform_int_distribution <T> (l, h) (rng); } 
template <class T> T rand(T h) { return uniform_int_distribution <T> (0, h - 1) (rng); } 

// end of template


const int MAX = 4123;

int N, M, K, A[MAX][MAX];

void init(void) {
	cin >> N >> M >> K;
	REP(i, N) REP(j, M) {
		char c; cin >> c;
		A[i][j] = c == 'A' ? 3 : c == 'T' ? 2 : c == 'G';
	}
}

long long val[MAX], sum[MAX][4];

void process(void) {
	vector <int> res;
	while (res.size() != 1) {
		res.clear();
		memset(sum, 0, sizeof(sum));
		long long total = 0;
		REP(i, N) {
			val[i] = rand(1LL, (long long) 1e18);
			total += val[i];
			REP(j, M) sum[j][A[i][j]] += val[i];
		}
		REP(i, N) {
			long long cur = 0;
			REP(j, M) cur += total - sum[j][A[i][j]];
			if (cur == K * (total - val[i])) res.push_back(i);
		}
	}
	cout << res[0] + 1 << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("C");
	init();
	process();
	cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

genetics.cpp: In function 'int main()':
genetics.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:86:2: note: in expansion of macro 'file'
   86 |  file("C");
      |  ^~~~
genetics.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
genetics.cpp:86:2: note: in expansion of macro 'file'
   86 |  file("C");
      |  ^~~~

Subtask #1
27.0 / 27.0

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

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 19284 KB Output is correct
2 Correct 80 ms 23500 KB Output is correct
3 Correct 86 ms 22536 KB Output is correct
4 Correct 18 ms 8388 KB Output is correct
5 Correct 81 ms 23524 KB Output is correct
6 Correct 83 ms 23500 KB Output is correct
7 Correct 37 ms 10188 KB Output is correct
8 Correct 35 ms 10180 KB Output is correct
9 Correct 75 ms 21892 KB Output is correct
10 Correct 75 ms 21916 KB Output is correct
11 Correct 67 ms 19216 KB Output is correct
12 Correct 66 ms 19404 KB Output is correct
13 Correct 62 ms 19296 KB Output is correct
14 Correct 55 ms 16524 KB Output is correct
15 Correct 64 ms 16756 KB Output is correct
16 Correct 61 ms 17388 KB Output is correct
17 Correct 79 ms 22452 KB Output is correct
18 Correct 77 ms 22348 KB Output is correct
19 Correct 76 ms 22468 KB Output is correct
20 Correct 77 ms 22224 KB Output is correct
21 Correct 78 ms 22512 KB Output is correct
22 Correct 76 ms 22216 KB Output is correct
23 Correct 81 ms 22428 KB Output is correct
24 Correct 78 ms 22420 KB Output is correct
25 Correct 78 ms 22220 KB Output is correct
26 Correct 78 ms 22348 KB Output is correct
27 Correct 78 ms 22308 KB Output is correct
28 Correct 76 ms 22256 KB Output is correct
29 Correct 83 ms 22468 KB Output is correct
30 Correct 83 ms 23520 KB Output is correct
31 Correct 80 ms 23516 KB Output is correct
32 Correct 80 ms 23496 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 852 KB Output is correct
35 Correct 1 ms 468 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 19284 KB Output is correct
2 Correct 80 ms 23500 KB Output is correct
3 Correct 86 ms 22536 KB Output is correct
4 Correct 18 ms 8388 KB Output is correct
5 Correct 81 ms 23524 KB Output is correct
6 Correct 83 ms 23500 KB Output is correct
7 Correct 37 ms 10188 KB Output is correct
8 Correct 35 ms 10180 KB Output is correct
9 Correct 75 ms 21892 KB Output is correct
10 Correct 75 ms 21916 KB Output is correct
11 Correct 67 ms 19216 KB Output is correct
12 Correct 66 ms 19404 KB Output is correct
13 Correct 62 ms 19296 KB Output is correct
14 Correct 55 ms 16524 KB Output is correct
15 Correct 64 ms 16756 KB Output is correct
16 Correct 61 ms 17388 KB Output is correct
17 Correct 79 ms 22452 KB Output is correct
18 Correct 77 ms 22348 KB Output is correct
19 Correct 76 ms 22468 KB Output is correct
20 Correct 77 ms 22224 KB Output is correct
21 Correct 78 ms 22512 KB Output is correct
22 Correct 76 ms 22216 KB Output is correct
23 Correct 81 ms 22428 KB Output is correct
24 Correct 78 ms 22420 KB Output is correct
25 Correct 78 ms 22220 KB Output is correct
26 Correct 78 ms 22348 KB Output is correct
27 Correct 78 ms 22308 KB Output is correct
28 Correct 76 ms 22256 KB Output is correct
29 Correct 83 ms 22468 KB Output is correct
30 Correct 83 ms 23520 KB Output is correct
31 Correct 80 ms 23516 KB Output is correct
32 Correct 80 ms 23496 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 1 ms 852 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 343 ms 72664 KB Output is correct
37 Correct 388 ms 83084 KB Output is correct
38 Correct 417 ms 81156 KB Output is correct
39 Correct 146 ms 43468 KB Output is correct
40 Correct 393 ms 82924 KB Output is correct
41 Correct 199 ms 41644 KB Output is correct
42 Correct 194 ms 41648 KB Output is correct
43 Correct 279 ms 67936 KB Output is correct
44 Correct 387 ms 83072 KB Output is correct
45 Correct 387 ms 82896 KB Output is correct
46 Correct 409 ms 83008 KB Output is correct
47 Correct 337 ms 72704 KB Output is correct
48 Correct 348 ms 72684 KB Output is correct
49 Correct 293 ms 62352 KB Output is correct
50 Correct 295 ms 62300 KB Output is correct
51 Correct 333 ms 70224 KB Output is correct
52 Correct 385 ms 80908 KB Output is correct
53 Correct 413 ms 81004 KB Output is correct
54 Correct 370 ms 80744 KB Output is correct
55 Correct 387 ms 80664 KB Output is correct
56 Correct 382 ms 80584 KB Output is correct
57 Correct 420 ms 81172 KB Output is correct
58 Correct 455 ms 81216 KB Output is correct
59 Correct 425 ms 80748 KB Output is correct
60 Correct 420 ms 81228 KB Output is correct
61 Correct 414 ms 80860 KB Output is correct
62 Correct 403 ms 80408 KB Output is correct
63 Correct 409 ms 81164 KB Output is correct
64 Correct 424 ms 81092 KB Output is correct
65 Correct 407 ms 80856 KB Output is correct
66 Correct 415 ms 80920 KB Output is correct
67 Correct 413 ms 81220 KB Output is correct
68 Correct 401 ms 81160 KB Output is correct
69 Correct 395 ms 80808 KB Output is correct
70 Correct 433 ms 81060 KB Output is correct
71 Correct 413 ms 80708 KB Output is correct
72 Correct 404 ms 81396 KB Output is correct
73 Correct 388 ms 80796 KB Output is correct
74 Correct 1 ms 460 KB Output is correct
75 Correct 1 ms 852 KB Output is correct
76 Correct 1 ms 464 KB Output is correct

Subtask #4
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 1 ms 852 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 852 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 860 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 852 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 78 ms 19284 KB Output is correct
19 Correct 80 ms 23500 KB Output is correct
20 Correct 86 ms 22536 KB Output is correct
21 Correct 18 ms 8388 KB Output is correct
22 Correct 81 ms 23524 KB Output is correct
23 Correct 83 ms 23500 KB Output is correct
24 Correct 37 ms 10188 KB Output is correct
25 Correct 35 ms 10180 KB Output is correct
26 Correct 75 ms 21892 KB Output is correct
27 Correct 75 ms 21916 KB Output is correct
28 Correct 67 ms 19216 KB Output is correct
29 Correct 66 ms 19404 KB Output is correct
30 Correct 62 ms 19296 KB Output is correct
31 Correct 55 ms 16524 KB Output is correct
32 Correct 64 ms 16756 KB Output is correct
33 Correct 61 ms 17388 KB Output is correct
34 Correct 79 ms 22452 KB Output is correct
35 Correct 77 ms 22348 KB Output is correct
36 Correct 76 ms 22468 KB Output is correct
37 Correct 77 ms 22224 KB Output is correct
38 Correct 78 ms 22512 KB Output is correct
39 Correct 76 ms 22216 KB Output is correct
40 Correct 81 ms 22428 KB Output is correct
41 Correct 78 ms 22420 KB Output is correct
42 Correct 78 ms 22220 KB Output is correct
43 Correct 78 ms 22348 KB Output is correct
44 Correct 78 ms 22308 KB Output is correct
45 Correct 76 ms 22256 KB Output is correct
46 Correct 83 ms 22468 KB Output is correct
47 Correct 83 ms 23520 KB Output is correct
48 Correct 80 ms 23516 KB Output is correct
49 Correct 80 ms 23496 KB Output is correct
50 Correct 1 ms 468 KB Output is correct
51 Correct 1 ms 852 KB Output is correct
52 Correct 1 ms 468 KB Output is correct
53 Correct 343 ms 72664 KB Output is correct
54 Correct 388 ms 83084 KB Output is correct
55 Correct 417 ms 81156 KB Output is correct
56 Correct 146 ms 43468 KB Output is correct
57 Correct 393 ms 82924 KB Output is correct
58 Correct 199 ms 41644 KB Output is correct
59 Correct 194 ms 41648 KB Output is correct
60 Correct 279 ms 67936 KB Output is correct
61 Correct 387 ms 83072 KB Output is correct
62 Correct 387 ms 82896 KB Output is correct
63 Correct 409 ms 83008 KB Output is correct
64 Correct 337 ms 72704 KB Output is correct
65 Correct 348 ms 72684 KB Output is correct
66 Correct 293 ms 62352 KB Output is correct
67 Correct 295 ms 62300 KB Output is correct
68 Correct 333 ms 70224 KB Output is correct
69 Correct 385 ms 80908 KB Output is correct
70 Correct 413 ms 81004 KB Output is correct
71 Correct 370 ms 80744 KB Output is correct
72 Correct 387 ms 80664 KB Output is correct
73 Correct 382 ms 80584 KB Output is correct
74 Correct 420 ms 81172 KB Output is correct
75 Correct 455 ms 81216 KB Output is correct
76 Correct 425 ms 80748 KB Output is correct
77 Correct 420 ms 81228 KB Output is correct
78 Correct 414 ms 80860 KB Output is correct
79 Correct 403 ms 80408 KB Output is correct
80 Correct 409 ms 81164 KB Output is correct
81 Correct 424 ms 81092 KB Output is correct
82 Correct 407 ms 80856 KB Output is correct
83 Correct 415 ms 80920 KB Output is correct
84 Correct 413 ms 81220 KB Output is correct
85 Correct 401 ms 81160 KB Output is correct
86 Correct 395 ms 80808 KB Output is correct
87 Correct 433 ms 81060 KB Output is correct
88 Correct 413 ms 80708 KB Output is correct
89 Correct 404 ms 81396 KB Output is correct
90 Correct 388 ms 80796 KB Output is correct
91 Correct 1 ms 460 KB Output is correct
92 Correct 1 ms 852 KB Output is correct
93 Correct 1 ms 464 KB Output is correct
94 Correct 410 ms 78532 KB Output is correct
95 Correct 401 ms 83020 KB Output is correct
96 Correct 395 ms 81596 KB Output is correct
97 Correct 234 ms 44556 KB Output is correct
98 Correct 137 ms 43452 KB Output is correct
99 Correct 392 ms 82976 KB Output is correct
100 Correct 200 ms 41708 KB Output is correct
101 Correct 201 ms 41700 KB Output is correct
102 Correct 294 ms 68012 KB Output is correct
103 Correct 385 ms 82892 KB Output is correct
104 Correct 425 ms 83012 KB Output is correct
105 Correct 398 ms 82992 KB Output is correct
106 Correct 378 ms 78796 KB Output is correct
107 Correct 345 ms 72908 KB Output is correct
108 Correct 291 ms 62344 KB Output is correct
109 Correct 351 ms 71552 KB Output is correct
110 Correct 338 ms 69768 KB Output is correct
111 Correct 372 ms 82984 KB Output is correct
112 Correct 408 ms 81868 KB Output is correct
113 Correct 383 ms 80672 KB Output is correct
114 Correct 378 ms 80600 KB Output is correct
115 Correct 393 ms 80884 KB Output is correct
116 Correct 396 ms 81840 KB Output is correct
117 Correct 428 ms 82052 KB Output is correct
118 Correct 414 ms 81896 KB Output is correct
119 Correct 409 ms 81852 KB Output is correct
120 Correct 438 ms 82008 KB Output is correct
121 Correct 379 ms 72692 KB Output is correct
122 Correct 405 ms 83008 KB Output is correct
123 Correct 398 ms 81040 KB Output is correct
124 Correct 1 ms 468 KB Output is correct
125 Correct 1 ms 852 KB Output is correct
126 Correct 1 ms 468 KB Output is correct