Submission #64893

#TimeUsernameProblemLanguageResultExecution timeMemory
64893qkxwsmMartian DNA (IOI16_dna)C++17
100 / 100
19 ms752 KiB
/* PROG: source LANG: C++11 _____ .' '. / 0 0 \ | ^ | | \ / | \ '---' / '._____.' */ #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #include "dna.h" using namespace std; using namespace __gnu_pbds; struct chash { int operator()(int x) const { x ^= (x >> 20) ^ (x >> 12); return x ^ (x >> 7) ^ (x >> 4); } int operator()(long long x) const { return x ^ (x >> 32); } }; template<typename T> using orderedset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; template<typename T, typename U> using hashtable = gp_hash_table<T, U, chash>; template<class T> void readi(T &x) { T input = 0; bool negative = false; char c = ' '; while (c < '-') { c = getchar(); } if (c == '-') { negative = true; c = getchar(); } while (c >= '0') { input = input * 10 + (c - '0'); c = getchar(); } if (negative) { input = -input; } x = input; } template<class T> void printi(T output) { if (output == 0) { putchar('0'); return; } if (output < 0) { putchar('-'); output = -output; } int aout[20]; int ilen = 0; while(output) { aout[ilen] = ((output % 10)); output /= 10; ilen++; } for (int i = ilen - 1; i >= 0; i--) { putchar(aout[i] + '0'); } return; } template<class T> void ckmin(T &a, T b) { a = min(a, b); } template<class T> void ckmax(T &a, T b) { a = max(a, b); } template<class T, class U> T normalize(T x, U mod = 1000000007) { return (((x % mod) + mod) % mod); } long long randomizell(long long mod) { return ((1ll << 45) * rand() + (1ll << 30) * rand() + (1ll << 15) * rand() + rand()) % mod; } int randomize(int mod) { return ((1ll << 15) * rand() + rand()) % mod; } #define y0 ___y0 #define y1 ___y1 #define MP make_pair #define MT make_tuple #define PB push_back #define PF push_front #define LB lower_bound #define UB upper_bound #define fi first #define se second #define debug(x) cerr << #x << " = " << x << endl; const long double PI = 4.0 * atan(1.0); const long double EPS = 1e-10; #define MAGIC 347 #define SINF 10007 #define CO 1000007 #define INF 1000000007 #define BIG 1000000931 #define LARGE 1696969696967ll #define GIANT 2564008813937411ll #define LLINF 2696969696969696969ll typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ld, ld> pdd; string s; int turns = 0; int N; // bool make_test(string p) // { // // debug(p); // turns++; // if (p.length() > s.length()) return false; // for (int i = 0; i <= s.length() - p.length(); i++) // { // if (s.substr(i, p.length()) == p) return true; // } // // cerr << "false " << p << ' ' << s << endl; // return false; // } string dup(char c, int t) { string res; for (int i = 0; i < t; i++) { res += c; } return res; } string analyse(int n, int t) { N = n; string res; int lo = 0, hi = N; while(hi > lo) { int mid = (hi + lo + 1) / 2; if (make_test(dup('1', mid))) { lo = mid; } else { hi = mid - 1; } } if (lo == 0) { return dup('0', N); } if (lo == N) { return dup('1', N); } // cerr << "lo = " << lo << endl; res = dup('1', lo); int inrow = 0; for (int i = 0; i < N; i++) { // cerr << res << endl; res += '0'; if (make_test(res)) { inrow = 0; continue; } else { // cerr << "fail " << res << endl; res.back() = '1'; inrow++; // cerr << "inrow " << inrow << endl; // cerr << "fail "<< res << endl; if (inrow > lo) { // cerr << "blah " << res << endl; //need to backtrack // cerr << "now " << res << endl; break; } } } lo = 0; hi = res.length(); while(hi > lo) { int mid = (lo + hi + 1) / 2; if (make_test(res.substr(0, mid))) { lo = mid; } else { hi = mid - 1; } } res = res.substr(0, lo); // cerr << res << endl; while(res.size() < N) { res = '1' + res; if (!make_test(res)) { res[0] = '0'; } } return res; } // int32_t main() // { // ios_base::sync_with_stdio(0); // srand(time(0)); // // cout << fixed << setprecision(10); // // cerr << fixed << setprecision(10); // if (fopen("input.in", "r")) // { // freopen ("input.in", "r", stdin); // freopen ("output.out", "w", stdout); // } // // cin >> s; // // s = string(353, '1') + string(333, '0') + string(303, '1'); // // cerr << "huh tf\n"; // // cerr << "s = " << s << endl; // cout << analyse(s.length(), 1024) << '\n'; // cout << turns << " turns\n"; // // cerr << "time elapsed = " << (clock() / (CLOCKS_PER_SEC / 1000)) << " ms" << endl; // return 0; // }

Compilation message (stderr)

dna.cpp: In function 'std::__cxx11::string analyse(int, int)':
dna.cpp:236:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(res.size() < N)
               ~~~~~~~~~~~^~~
grader.cpp: In function 'bool make_test(std::__cxx11::string)':
grader.cpp:14:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++) {
                  ~~^~~~~~~~~~
grader.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= ss.size(); i++) {
                  ~~^~~~~~~~~~~~
grader.cpp:28:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (pr[i] == p.size()) {
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...