Submission #1143194

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143194		alexnicu	Walk (POI13_spa)	C++17	12 / 100	686 ms	7464 KiB

spa

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

bool existing_numbers[(1<<24) + 5];

int string_to_number( string s ) {
    int ans = 0, pow = 0;
    for ( int i = s.size() - 1; i >= 0; i-- ) {
        if ( s[i] == '1' ) {
            ans = ans + ( 1 << pow );
        }
        pow++;
    }
    return ans;
}

vector<int> search_neighbors(int x, int n) {
    vector<int> ans;
    int cx = x;
    for ( int i = n - 1; i >= 0; i-- ) {
       if ( x >= (1 << i) ){
        ans.push_back(cx - (1 << i));
        x -= (1 << i);
       }
       else
        ans.push_back(cx + (1 << i));
    }
    return ans;
}

int main() {
    int n, k;
    cin >> n >> k;
    string a, b;
    cin >> a >> b;
    int start, finish;
    start = string_to_number(a);
    finish = string_to_number(b);
    string s;
    for ( int i = 1; i <= k; i++ ) {
        cin >> s;
        existing_numbers[string_to_number(s)] = true;
    }
    if ( a == b )
    {
        cout << "TAK";
        return 0;
    }
    try{
        queue<int> q;
        q.push(start);
        existing_numbers[start] = true;
        while(!q.empty() && existing_numbers[finish] == false) {
            int elem = q.front();
            vector<int> ans = search_neighbors(elem, n);
            for (auto nr : ans) {
                if ( existing_numbers[nr] == false ) {
                   existing_numbers[nr] = true;
                   q.push(nr);
                }
            }
            q.pop();
        }
    }
    catch(const exception& e){
        cout << "TAK";
        return 0;
    }
    if ( existing_numbers[finish] == true )
        cout << "TAK";
    else
        cout << "NIE";
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13