HackerEarth Number Recovery problem solution YASH PAL, 31 July 2024 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