oj.uz

Submission #409231

# Submission time Handle Problem Language Result Execution time Memory
409231 2021-05-20T11:41:37 Z kwongweng Snake Escaping (JOI18_snake_escaping) C++17
5 / 100
 2000 ms 65540 KB 
#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

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];
      |         ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 11248 KB Output is correct
2 Correct 248 ms 11300 KB Output is correct
3 Correct 272 ms 11220 KB Output is correct
4 Correct 259 ms 11224 KB Output is correct
5 Correct 251 ms 11328 KB Output is correct
6 Correct 254 ms 11228 KB Output is correct
7 Correct 249 ms 11312 KB Output is correct
8 Correct 245 ms 11280 KB Output is correct
9 Correct 260 ms 11392 KB Output is correct
10 Correct 262 ms 11252 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 11248 KB Output is correct
2 Correct 248 ms 11300 KB Output is correct
3 Correct 272 ms 11220 KB Output is correct
4 Correct 259 ms 11224 KB Output is correct
5 Correct 251 ms 11328 KB Output is correct
6 Correct 254 ms 11228 KB Output is correct
7 Correct 249 ms 11312 KB Output is correct
8 Correct 245 ms 11280 KB Output is correct
9 Correct 260 ms 11392 KB Output is correct
10 Correct 262 ms 11252 KB Output is correct
11 Execution timed out 2054 ms 24340 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 11248 KB Output is correct
2 Correct 248 ms 11300 KB Output is correct
3 Correct 272 ms 11220 KB Output is correct
4 Correct 259 ms 11224 KB Output is correct
5 Correct 251 ms 11328 KB Output is correct
6 Correct 254 ms 11228 KB Output is correct
7 Correct 249 ms 11312 KB Output is correct
8 Correct 245 ms 11280 KB Output is correct
9 Correct 260 ms 11392 KB Output is correct
10 Correct 262 ms 11252 KB Output is correct
11 Execution timed out 2054 ms 24340 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 11248 KB Output is correct
2 Correct 248 ms 11300 KB Output is correct
3 Correct 272 ms 11220 KB Output is correct
4 Correct 259 ms 11224 KB Output is correct
5 Correct 251 ms 11328 KB Output is correct
6 Correct 254 ms 11228 KB Output is correct
7 Correct 249 ms 11312 KB Output is correct
8 Correct 245 ms 11280 KB Output is correct
9 Correct 260 ms 11392 KB Output is correct
10 Correct 262 ms 11252 KB Output is correct
11 Runtime error 487 ms 65540 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 11248 KB Output is correct
2 Correct 248 ms 11300 KB Output is correct
3 Correct 272 ms 11220 KB Output is correct
4 Correct 259 ms 11224 KB Output is correct
5 Correct 251 ms 11328 KB Output is correct
6 Correct 254 ms 11228 KB Output is correct
7 Correct 249 ms 11312 KB Output is correct
8 Correct 245 ms 11280 KB Output is correct
9 Correct 260 ms 11392 KB Output is correct
10 Correct 262 ms 11252 KB Output is correct
11 Execution timed out 2054 ms 24340 KB Time limit exceeded
12 Halted 0 ms 0 KB -