oj.uz

Submission #32010

# Submission time Handle Problem Language Result Execution time Memory
32010 2017-09-22T00:50:07 Z kdh9949 Walk (POI13_spa) C++14
12 / 100
 5000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, k;
ll s, e;
unordered_set<ll> fb, ss;
queue<ll> q;
const int lim = 5000005;

ll get(){
	char buf[62]; scanf("%s", buf);
	ll ret = 0;
	for(int i = n - 1, j = 0; i >= 0; i--, j++){
		ret += (buf[i] - '0') * (1LL << j);
	}
	return ret;
}

int main(){
	scanf("%d%d", &n, &k);
	s = get(); e = get();
	for(int i = 0; i < k; i++) fb.insert(get());
    q.push(s); ss.insert(s);
    while(!q.empty() && ss.size() < lim){
        ll cur = q.front(); q.pop();
        for(int i = 0; i < n; i++){
			ll t = cur ^ (1LL << i);
			if(ss.find(t) == ss.end() && fb.find(t) == fb.end()){
				ss.insert(t);
				q.push(t);
			}
        }
    }
    if(ss.find(e) != ss.end()){ puts("TAK"); return 0; }
    if(ss.size() < lim){ puts("NIE"); return 0; }
    ss.clear();
    queue<ll>().swap(q);
    q.push(e); ss.insert(e);
	while(!q.empty() && ss.size() < lim){
        ll cur = q.front(); q.pop();
        for(int i = 0; i < n; i++){
			ll t = cur ^ (1LL << i);
			if(ss.find(t) == ss.end() && fb.find(t) == fb.end()){
				ss.insert(t);
				q.push(t);
			}
        }
    }
    puts(ss.size() == lim ? "TAK" : "NIE");
}

Compilation message

spa.cpp: In function 'll get()':
spa.cpp:12:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  char buf[62]; scanf("%s", buf);
                                ^
spa.cpp: In function 'int main()':
spa.cpp:21:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2156 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Correct 0 ms 2156 KB Output is correct
4 Correct 9 ms 2728 KB Output is correct
5 Correct 9 ms 2728 KB Output is correct
6 Correct 0 ms 2024 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 0 ms 2024 KB Output is correct
10 Correct 0 ms 2024 KB Output is correct
11 Correct 129 ms 11116 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 12336 KB Output is correct
2 Correct 506 ms 14432 KB Output is correct
3 Execution timed out 5000 ms 134280 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2156 KB Output is correct
2 Execution timed out 5000 ms 262144 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2304 KB Output is correct
2 Correct 0 ms 2156 KB Output is correct
3 Memory limit exceeded 4923 ms 262144 KB Memory limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 6932 KB Output is correct
2 Execution timed out 5000 ms 192736 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 6140 KB Output is correct
2 Execution timed out 5000 ms 262144 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 10456 KB Output is correct
2 Execution timed out 5000 ms 151944 KB Execution timed out
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 10344 KB Output is correct
2 Correct 103 ms 6088 KB Output is correct
3 Execution timed out 5000 ms 162652 KB Execution timed out
4 Halted 0 ms 0 KB -