Submission #409231

#TimeUsernameProblemLanguageResultExecution timeMemory
409231kwongwengSnake Escaping (JOI18_snake_escaping)C++17
5 / 100
2054 ms65540 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef long double ld; typedef pair<ll, ll> pll; #define FOR(i, a, b) for(int i = a; i < b; i++) #define ROF(i, a, b) for(int i = a; i >= b; i--) #define ms memset #define pb push_back #define F first #define S second ll MOD = 1000000007; ll INF = 1000000000; ll power(ll base, ll n){ if (n == 0) return 1; if (n == 1) return base; ll halfn = power(base, n/2); if (n % 2 == 0) return (halfn * halfn) % MOD; return (((halfn * halfn) % MOD) * base) % MOD; } ll inverse(ll n){ return power(n, MOD-2); } ll add(ll a, ll b){ return (a+b) % MOD; } ll mul(ll a, ll b){ return (a*b) % MOD; } ll gcd(ll a, ll b){ if (a == 0) return b; if (a == 1) return 1; return gcd(b%a, a); } int main(){ ios::sync_with_stdio(false); int n, q; cin >> n >> q; map<char, int> mp; string s; cin >> s; string num = "0123456789"; FOR(i, 0, 10) mp[num[i]] = i; int p[n+1]; FOR(i, 0, n+1) p[i] = (1<<i); int B = p[n]; map<string, int> mp1, used1; vector<string> bfs; FOR(i, 0, p[n]){ string t = ""; ROF(j, n-1, 0){ if ((i/p[j]) % 2 == 1){ t += "1"; }else{ t += "0"; } } mp1[t] = mp[s[i]]; ROF(j, n-1, 0){ char temp = t[j]; t[j] = '?'; if (used1[t] == 0) bfs.pb(t); used1[t] = 1; t[j] = temp; } } FOR(i, 0, bfs.size()){ string t = bfs[i]; FOR(j, 0, n){ if (t[j] == '?'){ int ans = 0; t[j] = '0'; ans += mp1[t]; t[j] = '1'; ans += mp1[t]; t[j] = '?'; mp1[t] = ans; break; } } ROF(j, n-1, 0){ if (t[j] != '?'){ char temp = t[j]; t[j] = '?'; if (used1[t] == 0) bfs.pb(t); used1[t] = 1; t[j] = temp; } } } while (q--){ string t; cin >> t; cout << mp1[t] << '\n'; } }

Compilation message (stderr)

snake_escaping.cpp: In function 'int main()':
snake_escaping.cpp:9:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, a, b) for(int i = a; i < b; i++)
......
   73 |     FOR(i, 0, bfs.size()){
      |         ~~~~~~~~~~~~~~~~               
snake_escaping.cpp:73:5: note: in expansion of macro 'FOR'
   73 |     FOR(i, 0, bfs.size()){
      |     ^~~
snake_escaping.cpp:52:9: warning: unused variable 'B' [-Wunused-variable]
   52 |     int B = p[n];
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...