Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1800 | [P1][P2]
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1800
Where Are My Keys
By Carlos Andrade, UFMS 
Brazil
Timelimit: 2
Gabriel works as Software Engineer at the Fingerbook Inc. On the last week he had a lot of work to do. So he decided to sleep at the FingerBook the whole week. After he finished his job, he decided to leave. then he realized he has lost his keys from home, so he decided to come back to pick up the keys.
Gabriel decided to start looking in which office that he was recently, After looking in all of the offices that he was in the last two days he hasn’t found the keys yet. So he decided to ask you to help him to search for the keys again. So he’ll tell you which ones of the offices that he was in the last week.
Help him to find the keys telling him in which offices is possible to find the keys.
Input
The first line contains two integers Q(1 ≤ Q ≤ 1*103) and E(1 ≤ E ≤ Q) representing respectively the number of offices that he was in the last week and the number of offices that he was in the last two days.
The second line contains E integers Si (1 ≤ Si ≤ 1000) containing the Identification number of each office that he was in the last two days.
The next line contains Q integers Ci (1 ≤ Ci ≤ 1000) containing the identification number of each one of the offices that he was in the last week.
Output
For each office that he was in the last week your program should return “0” in case he has already visited that office while looking for the keys. Else your program should return “1” in case he hasn't visited that office yet while he was looking for the keys.
| Input Sample | Output Sample |
|
10 5 1 15 5 998 27 1 88 15 88 99 5 100 7 27 998 |
0 1 0 0 1 0 1 1 0 0 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#define true 1
#define false 0
#define MAX 1100
int main (void)
{
unsigned short vetor[MAX];
unsigned short i, q, e, tmp;
while (scanf("%hu %hu", &q, &e) != EOF)
{
for (i = 0; i < e; ++i)
scanf("%hu", &tmp), vetor[tmp] = tmp;
for (i = 0; i < q; ++i)
{
scanf("%hu", &tmp);
if (tmp == vetor[tmp])
printf("0\n");
else
printf("1\n"), vetor[tmp] = tmp;
}
}
}
Input
1 15 5 998 27
1
88
15
88
99
5
100
7
27
998
Output
1
0
0
1
0
1
1
0
0
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define mp make_pair
#define pb push_back
#define MAXV 200100
using namespace std;
typedef vector<int> vi;
typedef pair < int, int> ii;
typedef long long int64;
map < int, int> offices;
int main()
{
ios::sync_with_stdio(false);
int q, e;
cin >> q >> e;
for (int i = 0; i < e; i++) {
int x;
cin >> x;
offices[x] = i;
}
for (int i = 0; i < q; i++) {
int x;
cin >> x;
if (offices.count(x))
cout << "0\n";
else {
offices[x] = 0;
cout << "1\n";
}
}
return 0;
}
Input
1 15 5 998 27
1
88
15
88
99
5
100
7
27
998
Output
1
0
0
1
0
1
1
0
0