oj.uz

Submission #93495

# Submission time Handle Problem Language Result Execution time Memory
93495 2019-01-08T19:26:58 Z Jatana Snake Escaping (JOI18_snake_escaping) C++17
22 / 100
 916 ms 16888 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)260];


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());
};

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;

string s;
int get(int i) {
	return s[i] - '0';
}
int n, N;
vector<int> subsum;
vector<int> highsum;

void calc(int l, int r) {
	if (l + 1 == r) {
		subsum[l] = get(l);
		highsum[l] = get(l);
	} else {
		int m = (l + r) / 2;
		calc(l, m);
		calc(m, r);
		int sh = (r - l) / 2;
		for (int i = m; i < r; i++) {
			subsum[i] += subsum[i - sh];
		}
		for (int i = l; i < m; i++) {
			highsum[i] += highsum[i + sh];
		}
	}
}

string to_bin(int mask) {
	string t = "";
	f(i, n) {
		t.pb('0' + (((1 << i) & mask) ? 1 : 0));
	}
	return t;
}
signed main(signed argc, char *argv[]) {
	int Q;
	scan n, Q;
	N = (1 << n);
	subsum.resize(N);
	highsum.resize(N);
	scan s;
	calc(0, N);

	f(i, Q) {
		string mask;
		scan mask;
		reverse(mask.begin(), mask.end());
		int mz = 0, mo = 0, mu = 0;
		f(j, len(mask)) {
			if (mask[j] == '0') {
				mz |= (1 << j);
			} else if (mask[j] == '1') {
				mo |= (1 << j);
			} else {
				mu |= (1 << j);
			}
		}
		if (__builtin_popcount(mo) <= 7) {
			int rez = 0;
			for (int m = mo; m > 0; m = ((m - 1) & mo)) {
				rez += subsum[m | mu] * ((__builtin_popcount(m) & 1) ? 1 : -1);
			}
			rez -= subsum[mu];
			print abs(rez);
		} else if (__builtin_popcount(mu) <= 7) {
			int rez = 0;
			for (int m = mu; m > 0; m = ((m - 1) & mu)) {
				rez += get(m | mo);
			}
			rez += get(mo);
			print abs(rez);
		} else {
			int rez = 0;
			for (int m = mz; m > 0; m = ((m - 1) & mz)) {
				rez += highsum[m | mo] * ((__builtin_popcount(m) & 1) ? 1 : -1);
			}
			rez -= highsum[mo];
			print abs(rez);
		}
	}
}

Compilation message

snake_escaping.cpp: In function 'void fast_scan(int&)':
snake_escaping.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); }
                          ~~~~~^~~~~~~~~~
snake_escaping.cpp: In function 'void fast_scan(long long int&)':
snake_escaping.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); }
                                ~~~~~^~~~~~~~~~~~
snake_escaping.cpp: In function 'void fast_scan(long long unsigned int&)':
snake_escaping.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); }
                                         ~~~~~^~~~~~~~~~~~
snake_escaping.cpp: In function 'void fast_scan(double&)':
snake_escaping.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); }
                             ~~~~~^~~~~~~~~~~
snake_escaping.cpp: In function 'void fast_scan(long double&)':
snake_escaping.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); }
                                  ~~~~~^~~~~~~~~~~
snake_escaping.cpp: In function 'void fast_scan(char&)':
snake_escaping.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%c", &x); 
  ~~~~~^~~~~~~~~~
snake_escaping.cpp: In function 'void fast_scan(std::__cxx11::string&)':
snake_escaping.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);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 462 ms 4708 KB Output is correct
12 Correct 349 ms 4432 KB Output is correct
13 Correct 397 ms 3744 KB Output is correct
14 Correct 388 ms 3680 KB Output is correct
15 Correct 371 ms 4600 KB Output is correct
16 Correct 440 ms 3996 KB Output is correct
17 Correct 444 ms 3968 KB Output is correct
18 Correct 301 ms 5644 KB Output is correct
19 Correct 458 ms 2808 KB Output is correct
20 Correct 523 ms 4492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 462 ms 4708 KB Output is correct
12 Correct 349 ms 4432 KB Output is correct
13 Correct 397 ms 3744 KB Output is correct
14 Correct 388 ms 3680 KB Output is correct
15 Correct 371 ms 4600 KB Output is correct
16 Correct 440 ms 3996 KB Output is correct
17 Correct 444 ms 3968 KB Output is correct
18 Correct 301 ms 5644 KB Output is correct
19 Correct 458 ms 2808 KB Output is correct
20 Correct 523 ms 4492 KB Output is correct
21 Correct 664 ms 4772 KB Output is correct
22 Correct 382 ms 4856 KB Output is correct
23 Correct 484 ms 3960 KB Output is correct
24 Correct 482 ms 3804 KB Output is correct
25 Correct 416 ms 5752 KB Output is correct
26 Correct 554 ms 4220 KB Output is correct
27 Correct 547 ms 4344 KB Output is correct
28 Correct 337 ms 6960 KB Output is correct
29 Correct 916 ms 3068 KB Output is correct
30 Correct 603 ms 5152 KB Output is correct
31 Correct 474 ms 4856 KB Output is correct
32 Correct 483 ms 4984 KB Output is correct
33 Correct 396 ms 3716 KB Output is correct
34 Correct 553 ms 4088 KB Output is correct
35 Correct 537 ms 4344 KB Output is correct
36 Correct 324 ms 3064 KB Output is correct
37 Correct 372 ms 4728 KB Output is correct
38 Correct 589 ms 2808 KB Output is correct
39 Correct 670 ms 3832 KB Output is correct
40 Correct 525 ms 3704 KB Output is correct

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Runtime error 18 ms 16888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 462 ms 4708 KB Output is correct
12 Correct 349 ms 4432 KB Output is correct
13 Correct 397 ms 3744 KB Output is correct
14 Correct 388 ms 3680 KB Output is correct
15 Correct 371 ms 4600 KB Output is correct
16 Correct 440 ms 3996 KB Output is correct
17 Correct 444 ms 3968 KB Output is correct
18 Correct 301 ms 5644 KB Output is correct
19 Correct 458 ms 2808 KB Output is correct
20 Correct 523 ms 4492 KB Output is correct
21 Correct 664 ms 4772 KB Output is correct
22 Correct 382 ms 4856 KB Output is correct
23 Correct 484 ms 3960 KB Output is correct
24 Correct 482 ms 3804 KB Output is correct
25 Correct 416 ms 5752 KB Output is correct
26 Correct 554 ms 4220 KB Output is correct
27 Correct 547 ms 4344 KB Output is correct
28 Correct 337 ms 6960 KB Output is correct
29 Correct 916 ms 3068 KB Output is correct
30 Correct 603 ms 5152 KB Output is correct
31 Correct 474 ms 4856 KB Output is correct
32 Correct 483 ms 4984 KB Output is correct
33 Correct 396 ms 3716 KB Output is correct
34 Correct 553 ms 4088 KB Output is correct
35 Correct 537 ms 4344 KB Output is correct
36 Correct 324 ms 3064 KB Output is correct
37 Correct 372 ms 4728 KB Output is correct
38 Correct 589 ms 2808 KB Output is correct
39 Correct 670 ms 3832 KB Output is correct
40 Correct 525 ms 3704 KB Output is correct
41 Runtime error 18 ms 16888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Halted 0 ms 0 KB -