답안 #93495 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93495	2019-01-08T19:26:58 Z	Jatana	Snake Escaping (JOI18_snake_escaping)	C++17	22 / 100	916 ms	16888 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;
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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #93495

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 7.0 / 7.0

Subtask #3 10.0 / 10.0

Subtask #4 0 / 53.0

Subtask #5 0 / 25.0

Subtask #1
5.0 / 5.0

Subtask #2
7.0 / 7.0

Subtask #3
10.0 / 10.0

Subtask #4
0 / 53.0

Subtask #5
0 / 25.0