HackerEarth Number Recovery problem solution

In this HackerEarth Number Recovery problem solution A positive integer X has been stolen. But luckily, N hints are available, each described by two integers ai and di, meaning that |X – ai| = di. The hints are numbered 1 through N. While some of those hints are helpful, some might be just a lie. Therefore, we are going to investigate the number X under different possible scenarios.

Initially, we neither trust nor distrust any hint. That is, each hint may be either true or false. Then, in each of the Q stages, we will either:

1 id

Entrust the -th hint (1 <= id <= N). That is, from now on, the -th hint must be true, unless declared otherwise in the future.

2 id

Distrust the -th hint (1 <= id <= N). That is, from now on, the -th hint must be false, unless declared otherwise in the future.

3 id

Neutralize the -th hint (1 <= id <= N). That is, from now on, the -th hint may be either true or false, unless declared otherwise in the future.

After each stage, you should determine the number of possible positive values X and report such values in increasing order. If there are infinitely many such values, print -1 instead.

HackerEarth Number Recovery problem solution.

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <assert.h>
#include <iostream>
using namespace std;

map<int, int> ok;
map<int, int> ban;

queue<int> q;

int main(){
    int M, K;
    scanf("%d%d", &M, &K);
    vector<int> x(M+1), d(M+1);
    vector<int> status(M+1, 0);
    for(int i=1; i<=M; i++) scanf("%d%d", &x[i], &d[i]);
    int entrusted = 0;
    for(int i=0; i<K; i++){
        int t, id;
        scanf("%d%d", &t, &id);
        int a = x[id]-d[id], b = x[id]+d[id];
        if(status[id] == 1){
            ok[a]--;
            if(a != b) ok[b]--;
            entrusted--;
        } else if(status[id] == 2){
            ban[a]--;
            ban[b]--;
        }
        status[id] = (t == 3 ? 0 : t);
        if(t == 1){
            ok[a]++;
            if(a != b) ok[b]++;
            entrusted++;
            q.push(id);
        } else if(t == 2){
            ban[a]++;
            ban[b]++;
        }
        // get the answer
        int idx = -1;
        while(!q.empty()){
            int x = q.front();
            if(status[x] == 1){
                idx = x;
                break;
            }
            q.pop();
        }
        if(idx == -1) printf("-1n");
        else{
            int a = x[idx]-d[idx];
            int b = x[idx]+d[idx];
            vector<int> res;
            if(a > 0 && ok[a] == entrusted && ban[a] == 0) res.push_back(a);
            if(b > a && ok[b] == entrusted && ban[b] == 0) res.push_back(b);
            printf("%d", (int)res.size());
            for(int i=0; i<res.size(); i++){
                printf(" %d", res[i]);
            }
            printf("n");
        }
    }
    return 0;
}

Second solution

#include "bits/stdc++.h"
using namespace std;

map<int,int> bad, good;
multiset<vector<int>> good_pairs;

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    vector<vector<int>> info(n);
    for(int i = 0; i < n; ++i) {
        int x, d;
        scanf("%d%d", &x, &d);
        info[i] = {x - d, x + d};
        if(x - d == x + d) {
            info[i].pop_back();
        }
    }
    vector<int> state(n);
    // bad: -1
    // neutral: 0
    // trusted: 1
    while(q--) {
        int type, i;
        scanf("%d%d", &type, &i);
        --i;
        // 1) erase the current state
        if(state[i] == -1) {
            for(int a : info[i]) {
                --bad[a];
            }
        }
        if(state[i] == 1) {
            for(int a : info[i]) {
                --good[a];
            }
            good_pairs.erase(good_pairs.find(info[i]));
        }
        // 2) add a new state
        if(type == 1) state[i] = 1;
        else if(type == 2) state[i] = -1;
        else if(type == 3) state[i] = 0;
        else assert(false);
        if(state[i] == -1) {
            for(int a : info[i]) {
                ++bad[a];
            }
        }
        if(state[i] == 1) {
            for(int a : info[i]) {
                ++good[a];
            }
            good_pairs.insert(info[i]);
        }
        if(good_pairs.empty()) {
            puts("-1");
            continue;
        }
        set<int> answer; // set doesn't count twice
        for(int a : *good_pairs.begin()) {
            if(!bad[a] && a > 0 && good[a] == (int) good_pairs.size()) {
                answer.insert(a);
            }
        }
        printf("%d", (int) answer.size());
        for(int a : answer) {
            printf(" %d", a);
        }
        puts("");
    }
}

coding problems