Submission #93494

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
93494	2019-01-08T19:23:18 Z	Jatana	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	1449 ms	18040 KB

snake_escaping

/*
                                                                                                     
                                             `-:://:::-                                             
                                           `//:-------:/:`                                          
                                          .+:--.......--:+`                                         
                                         `+:--..`````..--//`                                        
                                         .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;

void calc(int l, int r) {
	if (l + 1 == r) {
		subsum[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];
		}
	}
}

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);
	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) <= 10) {
			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) <= 10) {
			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 )
		}
	}
}

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	252 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	476 ms	4272 KB	Output is correct
12	Correct	379 ms	3964 KB	Output is correct
13	Correct	412 ms	3124 KB	Output is correct
14	Correct	404 ms	3448 KB	Output is correct
15	Correct	380 ms	4308 KB	Output is correct
16	Correct	446 ms	3540 KB	Output is correct
17	Correct	451 ms	3444 KB	Output is correct
18	Correct	296 ms	5368 KB	Output is correct
19	Correct	469 ms	2296 KB	Output is correct
20	Correct	613 ms	3880 KB	Output is correct

Subtask #3

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	476 ms	4272 KB	Output is correct
12	Correct	379 ms	3964 KB	Output is correct
13	Correct	412 ms	3124 KB	Output is correct
14	Correct	404 ms	3448 KB	Output is correct
15	Correct	380 ms	4308 KB	Output is correct
16	Correct	446 ms	3540 KB	Output is correct
17	Correct	451 ms	3444 KB	Output is correct
18	Correct	296 ms	5368 KB	Output is correct
19	Correct	469 ms	2296 KB	Output is correct
20	Correct	613 ms	3880 KB	Output is correct
21	Correct	667 ms	4284 KB	Output is correct
22	Correct	393 ms	4484 KB	Output is correct
23	Correct	495 ms	3448 KB	Output is correct
24	Correct	496 ms	3472 KB	Output is correct
25	Correct	437 ms	5308 KB	Output is correct
26	Correct	584 ms	3928 KB	Output is correct
27	Correct	600 ms	3904 KB	Output is correct
28	Correct	327 ms	6920 KB	Output is correct
29	Correct	921 ms	3164 KB	Output is correct
30	Correct	1117 ms	5108 KB	Output is correct
31	Correct	499 ms	5100 KB	Output is correct
32	Correct	492 ms	4964 KB	Output is correct
33	Correct	1449 ms	3868 KB	Output is correct
34	Correct	585 ms	3960 KB	Output is correct
35	Correct	603 ms	4256 KB	Output is correct
36	Correct	321 ms	15648 KB	Output is correct
37	Correct	386 ms	18040 KB	Output is correct
38	Correct	1196 ms	16192 KB	Output is correct
39	Correct	687 ms	17400 KB	Output is correct
40	Correct	553 ms	17144 KB	Output is correct

Subtask #4

0 / 53.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Runtime error	9 ms	8696 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	252 KB	Output is correct
2	Correct	2 ms	256 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	420 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	256 KB	Output is correct
8	Correct	2 ms	256 KB	Output is correct
9	Correct	2 ms	256 KB	Output is correct
10	Correct	2 ms	256 KB	Output is correct
11	Correct	476 ms	4272 KB	Output is correct
12	Correct	379 ms	3964 KB	Output is correct
13	Correct	412 ms	3124 KB	Output is correct
14	Correct	404 ms	3448 KB	Output is correct
15	Correct	380 ms	4308 KB	Output is correct
16	Correct	446 ms	3540 KB	Output is correct
17	Correct	451 ms	3444 KB	Output is correct
18	Correct	296 ms	5368 KB	Output is correct
19	Correct	469 ms	2296 KB	Output is correct
20	Correct	613 ms	3880 KB	Output is correct
21	Correct	667 ms	4284 KB	Output is correct
22	Correct	393 ms	4484 KB	Output is correct
23	Correct	495 ms	3448 KB	Output is correct
24	Correct	496 ms	3472 KB	Output is correct
25	Correct	437 ms	5308 KB	Output is correct
26	Correct	584 ms	3928 KB	Output is correct
27	Correct	600 ms	3904 KB	Output is correct
28	Correct	327 ms	6920 KB	Output is correct
29	Correct	921 ms	3164 KB	Output is correct
30	Correct	1117 ms	5108 KB	Output is correct
31	Correct	499 ms	5100 KB	Output is correct
32	Correct	492 ms	4964 KB	Output is correct
33	Correct	1449 ms	3868 KB	Output is correct
34	Correct	585 ms	3960 KB	Output is correct
35	Correct	603 ms	4256 KB	Output is correct
36	Correct	321 ms	15648 KB	Output is correct
37	Correct	386 ms	18040 KB	Output is correct
38	Correct	1196 ms	16192 KB	Output is correct
39	Correct	687 ms	17400 KB	Output is correct
40	Correct	553 ms	17144 KB	Output is correct
41	Runtime error	9 ms	8696 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
42	Halted	0 ms	0 KB	-