Submission #97930

# Submission time Handle Problem Language Result Execution time Memory
97930 2019-02-19T14:27:33 Z Jatana Selling RNA Strands (JOI16_selling_rna) C++17
60 / 100
1500 ms 176804 KB
/*
                                                                                                     
                                             `-:://:::-                                             
                                           `//:-------:/:`                                          
                                          .+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .o:--..`` ``..--:o`                                        
                                         .o:--...```..---+/`                                        
                                       `/y+o/---....---:+o.                                         
                                   `...````-os+/:---:/+o/--.`                                       
              `-/+++++/:.      `...`       :h+d+oooo+/+-`   ...                                     
            `/++//:::://++-`....`         -.`//````````:`     `..`                                  
           `o+/::------://o/`           `-` -.          -`       `..`                               
 `---.-o/:./o/::-..``..-ЗАПУСКАЕМ      ..  ..            -`        `...       ``..``                
  `....o+:-++/:--.```..-://s.        `-`  .-              -`          `-o: .-//::::/:-`             
          `:s+/:--....-::/+s-`      .-   `-                -`           -///:--------:/:`           
           ./s+//:::::://oo-``..НЕЙРОННУЮ: СЕТЬ:::::::-`РАБОТЯГИ        `+:--........--:/`          
            .:ooo+++++osso-`    `.:-...`/` ./::-------:/:`   -`         :+--..``````.--:+:...-+:-`  
             `.-/+++++/+-.-`    -.   ``:so:/:--.......--:+`  `-```````o+/+--..`````..--:o/-..:s+:.  
                 ```````:``.. `-`     -` `+:--..`````..--/+-.../.`````..-o:--.......---/o.    `     
                        `:  `:-      -.  .o:--..`` ``..--:o`   `-`      `:o+:--------:+o-`          
                         `-`-...    ..   .o/--...```..--:+/`    `-`     `oy/so/////++o/.`           
                          -/`  `-` `- ``+s/o/:---...---:++.      `-`   .-../d://///:-.`             
                `.---..``-..-    .-/..`````-oo+/:::::/+o+-        `-``-`  `-.  ````                 
             `:++++/+++++-  ..``.-/:`      /y-:/++o++/:.`..`       ./.   `-                         
            -++/::::::://+/..:-``:` ..   `-.`  ```.```    `..`   `..`-` `-                          
       ``  -o//:--....-::/++` -.-`   `-`.-`                 `..`..`  `-.-                           
  -----ss+:++/:--.```..-://s.  /.     `::                    `-:.     ./`                           
  `````/:..+o/::-..``.--:/+s. ..-`   `-``-`                 ..` `-`  `-`-`                          
          `-s+/::-----::/+oo---``-` ..    .:-    ```      .-`     .-.-  `-`                         
           `:oo+//::://+os/..:`..-/:`      :y.-:::::::.`.-`        ./-`  `-`                        
            `./+oooooooo+/.`-    .-:...`.. .//:-------://`        `- `..` `:.                       
              ``.-::::-.``-/`  `-` `-  `oo:+:--.......--:/`      `-    `.:--h.``..```               
                          -.-`.-    .-   `+:--..`````..--//`    `-       /s-//::::::::.             
                         -` `/-      ..  .o:--..`` ``..--:o.```.-        `//:--------://`           
                        -` .-`.-`     -.`-o/--...```..--:+/.``-:....``:-.+:--....`...--:+`          
                       ..`-.   `-.   ``:os:o/:---...---:++.  `-     ``///+:-..``````.--:+-````-.`   
              `.:///////.-`      .:-..` -``-+o+/:::::/+o/.  `-         `:+:-..`````..--:o/:--/ys+-  
            `-++///////+o/. ``....`-.    :` `.:++++++/:.`  .-           -o/---......---/o.   `.`    
           `++//:-----::/+o:..`     .-`   :    ```````    .-           `+so+:--------:++-`          
  `````:-``:o/::-..`..--:/+o`         -.  `-             .-          `../../+o+////+o+:.`           
  -----syo/o+/:--.```..-://s.          .-` `-           .-        `...     ``-:////:-``             
       .` `/s//:--....-::/+s.            -. `-`        .-       `..`                                
           .+o+/:::--:://+s/-..`          .::+y  ```  .-     `..`                                   
            ./oo++////+oso-`   `....       :y-+:::::::/`   ...                                      
             `.:+oooooo/-`         `....-. .//:-------:/:-.`                                        
                ``...``                 /+:+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .o:--..`` ``..--:o`                                        
                                         .+/--...```..--:+/`                                        
                                         `-o/:---...---:++.                                         
                                          `-+o+/:---:/+o/.                                          
                                            `.:+oooo+/-.`                                           
                                               ``````                                               
*/

#ifdef aimbot
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <ostream>
#include <istream>
#include <typeinfo>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <limits>
#include <fstream>
#include <array>
#include <list>
#include <bitset>
#include <functional>
#include <random>
#include <cstring>
#include <chrono>

#define random escape__from__random__aetuhoetnuhshe
#define mt make_tuple
#define x first
#define y second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define umap unordered_map
#define uset unordered_set
#define elif else if
#define len(v) ((int)v.size())
#define f(i, n) for (int i = 0; i < (n); i++)
#define rof(i, n) for (int i = ((n) - 1); i >= 0; i--) 
#define apply(v, act) for (auto &x : v) { act; }
#define log(args...) {string s = #args;deque<string> deq;\
string buf = "";int bal = 0;for (char c : s) {\
if (c == '(' || c == '[' || c == '{') {bal++;\
} else if (c == ')' || c == ']' || c == '}') {\
bal--;} else {if (bal == 0) {if (c == ',') {\
deq.pb(buf);buf = "";} else {if (c != ' ') {\
buf += c;}}}}}if (!buf.empty()) {deq.pb(buf);}\
smart_io::precall_print();smart_io::_print(deq, args);}

#define print    \
smart_io::precall_print(); \
cout,

#define scan cin,

#ifdef fast_allocator
const int MAXMEM = 200 * 1000 * 1024;
char _memory[MAXMEM];
size_t _ptr = 0;
void* operator new(size_t _x) { _ptr += _x; assert(_ptr < MAXMEM); return _memory + _ptr - _x; }
void operator delete (void*) noexcept {}
#endif

using namespace std;

char string_in_buffer[(int)2e5];


void fast_scan(int &x) { scanf("%d", &x); }
void fast_scan(long long &x) { scanf("%lld", &x); }
void fast_scan(unsigned long long &x) { scanf("%llu", &x); }
void fast_scan(double &x) { scanf("%lf", &x); }
void fast_scan(long double &x) { scanf("%Lf", &x); }
void fast_scan(char &x) { 
	scanf("%c", &x); 
	if (x == '\n') {
		fast_scan(x);
	}
}
void fast_scan(string &x) {
	scanf("%s", string_in_buffer);
	x = string(string_in_buffer);
}

template<class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
	fast_scan(p.first);
	fast_scan(p.second);
}

template <class T>
void fast_scan(vector<T> &v) {
	for (auto &x : v) fast_scan(x);
}

void fast_print(const int &x) { printf("%d", x); }
void fast_print(const unsigned int &x) { printf("%u", x); }
void fast_print(const long long &x) { printf("%lld", x); }
void fast_print(const unsigned long long &x) { printf("%llu", x); }
void fast_print(const double &x) { printf("%.15lf", x); }
void fast_print(const long double &x) { printf("%.15Lf", x); }
void fast_print(const char &x) { printf("%c", x); };
void fast_print(const string &x) { printf("%s", x.c_str());}
void fast_print(const char v[]) { fast_print((string)v); }

template<class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
	fast_print(p.first);
	fast_print(' ');
	fast_print(p.second);
}

template <class T>
void fast_print(const vector<T> &v) {
	if (v.empty()) return;
	fast_print(v[0]);
	for (int i = 1; i < v.size(); i++) {
		fast_print(' ');
		fast_print(v[i]);
	}
}

template <class T>
void fast_print(const vector<vector<T>> &v) {
	if (v.empty()) return;
	fast_print(v[0]);
	for (int i = 1; i < v.size(); i++) {
		fast_print('\n');
		fast_print(v[i]);
	}
}

template <class T>
void fast_print(const T &v) {
	for (const auto &x : v) {
		fast_print(x);
		fast_print(' ');
	}
}


using namespace std;


namespace smart_io {
	string print_start = "";
	string sep = " ";
	bool first_print = false;

	void precall_print() {
		fast_print(print_start);
		print_start = "\n";
		first_print = true;
	}

	void _print(deque<string>) {}
	template<class T, class... Args>
	void _print(deque<string> names, T elem, Args... args) {
		if (!first_print) {
			fast_print("\n");
		} else {
			first_print = false;
		}
		fast_print(names.front());
		fast_print(" = ");
		fast_print(elem);
		names.pop_front();
		_print(names, args...);
	}
} //namespace smart_io


template <class T>
ostream &operator,(ostream &os, const T &object) {
	if (!smart_io::first_print) {
		fast_print(smart_io::sep);
	} else {
		smart_io::first_print = false;
	}
	fast_print(object);
	return os;
}

template <class T>
istream &operator,(istream &is, T &object) {
	fast_scan(object);
	return is;
}

namespace random {
	using namespace std::chrono;
	mt19937 rng(duration_cast< milliseconds >(
		system_clock::now().time_since_epoch()
	).count());
	uniform_real_distribution<> prob_dist(0.0, 1.0);
};

namespace typedefs {
	typedef long long ll;
	typedef unsigned long long ull;
	typedef pair<int, int> pii;
	typedef long double ld;
}

namespace numbers_operation {
	template<class T>
	T floor_mod(T a, T b) {
		if (a >= 0 && b >= 0) return a % b;
		if (a <= 0 && b <= 0) return a % b;
		return abs(b) - (abs(a) % abs(b));
	}
}

using namespace numbers_operation;
using namespace typedefs;
using namespace random;

int n, m;

const ll MOD = 10000000000000061;
const ll base = 179;

vector<ll> power;

struct Hasher {
	vector<ll> hash;
	vector<ll> rehash;
	Hasher(string s) {
		hash.resize(len(s));
		hash[0] = s[0];
		for (int i = 1; i < len(s); i++) {
			hash[i] = ((hash[i - 1] * base) + s[i]) % MOD;
		}
		reverse(s.begin(), s.end());
		rehash.resize(len(s));
		rehash[0] = s[0];
		for (int i = 1; i < len(s); i++) {
			rehash[i] = ((rehash[i - 1] * base) + s[i]) % MOD;
		}
	}
};

ll mul(ll a, ll b) {
	__int128 x = a;
	__int128 y = b;
	x *= y;
	__int128 __module = MOD;
	return x % __module;
}

const int LIM = 100;

// unordered_map<ll, int> calc;
vector<ll> calc;

signed main(signed argc, char *argv[]) {
	// calc.rehash((int)2e7);
	power.pb(1);
	for (int i = 0; i < 2e6 + 100; i++) {
		power.pb((power.back() * base) % MOD);
	}
	scan n, m;
	vector<Hasher> big;
	f(i, n) {
		string s;
		scan s;
		if (len(s) > LIM) {
			big.emplace_back(s);
		} else {
			Hasher hasher(s);
			for (int a = 1; a <= len(s); a++) {
				for (int b = 1; b <= len(s); b++) {
					ll A = hasher.hash[a - 1];
					ll B = hasher.rehash[b - 1];
					ll C = (A + mul(B, power[a + 1])) % MOD;
					// calc[C]++;
					calc.pb(C);
				}
			}
		}
	}
	sort(calc.begin(), calc.end());
	f(i, m) {
		int cnt = 0;
		string p, q;
		scan p, q;
		reverse(q.begin(), q.end());
		Hasher ph(p);
		Hasher pq(q);
		ll hp = ph.hash.back();
		ll hq = pq.hash.back();
		for (auto &t : big) {
			if (t.hash[len(p) - 1] == hp
					&& t.rehash[len(q) - 1] == hq) {
				cnt++;
			}
		}
		if (len(p) <= LIM && len(q) <= LIM) {
			ll C = (hp + mul(hq, power[len(p) + 1])) % MOD;
			cnt += upper_bound(calc.begin(), calc.end(), C) - lower_bound(calc.begin(), calc.end(), C);
		}
		print cnt;
	}
}

Compilation message

selling_rna.cpp: In function 'void fast_scan(int&)':
selling_rna.cpp:133:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(int &x) { scanf("%d", &x); }
                          ~~~~~^~~~~~~~~~
selling_rna.cpp: In function 'void fast_scan(long long int&)':
selling_rna.cpp:134:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(long long &x) { scanf("%lld", &x); }
                                ~~~~~^~~~~~~~~~~~
selling_rna.cpp: In function 'void fast_scan(long long unsigned int&)':
selling_rna.cpp:135:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(unsigned long long &x) { scanf("%llu", &x); }
                                         ~~~~~^~~~~~~~~~~~
selling_rna.cpp: In function 'void fast_scan(double&)':
selling_rna.cpp:136:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(double &x) { scanf("%lf", &x); }
                             ~~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void fast_scan(long double&)':
selling_rna.cpp:137:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void fast_scan(long double &x) { scanf("%Lf", &x); }
                                  ~~~~~^~~~~~~~~~~
selling_rna.cpp: In function 'void fast_scan(char&)':
selling_rna.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%c", &x); 
  ~~~~~^~~~~~~~~~
selling_rna.cpp: In function 'void fast_scan(std::__cxx11::string&)':
selling_rna.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", string_in_buffer);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 43 ms 16872 KB Output is correct
2 Correct 48 ms 16856 KB Output is correct
3 Correct 46 ms 16856 KB Output is correct
4 Correct 47 ms 16980 KB Output is correct
5 Correct 48 ms 16860 KB Output is correct
6 Correct 52 ms 16872 KB Output is correct
7 Correct 43 ms 16872 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 382 ms 59608 KB Output is correct
2 Correct 1163 ms 85308 KB Output is correct
3 Correct 592 ms 72192 KB Output is correct
4 Correct 952 ms 85564 KB Output is correct
5 Correct 1008 ms 65212 KB Output is correct
6 Correct 920 ms 65472 KB Output is correct
7 Correct 437 ms 42380 KB Output is correct
8 Correct 446 ms 47816 KB Output is correct
9 Correct 489 ms 47676 KB Output is correct
10 Correct 801 ms 48140 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 113 ms 19896 KB Output is correct
2 Correct 167 ms 29628 KB Output is correct
3 Correct 153 ms 24140 KB Output is correct
4 Correct 103 ms 22756 KB Output is correct
5 Correct 164 ms 29628 KB Output is correct
6 Correct 147 ms 24124 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 43 ms 16872 KB Output is correct
2 Correct 48 ms 16856 KB Output is correct
3 Correct 46 ms 16856 KB Output is correct
4 Correct 47 ms 16980 KB Output is correct
5 Correct 48 ms 16860 KB Output is correct
6 Correct 52 ms 16872 KB Output is correct
7 Correct 43 ms 16872 KB Output is correct
8 Correct 382 ms 59608 KB Output is correct
9 Correct 1163 ms 85308 KB Output is correct
10 Correct 592 ms 72192 KB Output is correct
11 Correct 952 ms 85564 KB Output is correct
12 Correct 1008 ms 65212 KB Output is correct
13 Correct 920 ms 65472 KB Output is correct
14 Correct 437 ms 42380 KB Output is correct
15 Correct 446 ms 47816 KB Output is correct
16 Correct 489 ms 47676 KB Output is correct
17 Correct 801 ms 48140 KB Output is correct
18 Correct 113 ms 19896 KB Output is correct
19 Correct 167 ms 29628 KB Output is correct
20 Correct 153 ms 24140 KB Output is correct
21 Correct 103 ms 22756 KB Output is correct
22 Correct 164 ms 29628 KB Output is correct
23 Correct 147 ms 24124 KB Output is correct
24 Execution timed out 1563 ms 176804 KB Time limit exceeded
25 Halted 0 ms 0 KB -