제출 #1143166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143166		alexnicu	새로운 문제 (POI13_spa)	C++20	12 / 100	495 ms	243380 KiB

spa

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

using namespace std;

bool existing_numbers[(1<<23)];

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;
}
int finish;
bool ans = false;
int n;
void dfs( int node ) {
    if (node == finish ) {
        ans = true;
        return;
    }
    int cx = node;
    for ( int i = n - 1; i >= 0; i-- ) {
       if ( node >= (1 << i) ){
        if(existing_numbers[cx - (1 << i)] == false){
            existing_numbers[cx - (1 << i)] = true;
            dfs(cx - (1 << i));
        }
        node -= (1 << i);
       }
       else
        if(existing_numbers[cx + (1 << i)] == false){
            existing_numbers[cx + (1 << i)] = true;
            dfs(cx + (1 << i));
        }
    }
    return;
}

int main() {
    int k;
    cin >> n >> k;
    string a, b;
    cin >> a >> b;
    int start;
    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;
    }
    existing_numbers[start] = true;
    dfs(start);
    if ( ans == 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