Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Frequency Array Retrieval CodeChef Solution
Problem -Frequency Array Retrieval CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Frequency Array Retrieval CodeChef Solution in C++17
#include <bits/stdc++.h>
using namespace std;
// Ordered set requirements
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<long long, null_type,less<long long>, rb_tree_tag,tree_order_statistics_node_update>
// Aliases
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vll = vector<long long>;
using vpll = vector<pair<long long, long long>>;
using pll = pair<long long, long long>;
// Constants
constexpr ll INF = 2e18;
constexpr ld EPS = 1e-9;
constexpr ll MOD = 1e9+7;
// Macros
#define F first
#define S second
#define PB push_back
#define POB pop_back
#define MP make_pair
#define all(x) begin(x), end(x)
#define allr(x) rbegin(x), rend(x)
#define int long long
#define for0(a, c) for (int(a) = 0; (a) < (c); (a)++)
#define forc(a, b, c) for (int(a) = (b); (a) <= (c); (a)++)
#define forr(a, b, c) for (int(a) = (b); (a) >= (c); (a)--)
// cin >> pair<T1, T2>
template<typename T1, typename T2>
istream& operator>>(istream &istream, pair<T1, T2> &p) {
return (istream >> p.first >> p.second);
}
// cin >> vector<T>
template<typename T>
istream& operator>>(istream &istream, vector<T> &v){
for (auto &it : v) cin >> it;
return istream;
}
// cout << pair<T1, T2>
template<typename T1, typename T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p){
return (ostream << p.first << " " << p.second);
}
// cout << vector<T>
template<typename T>
ostream& operator<<(ostream &ostream, const vector<T> &c) {
for (auto &it : c) cout << it << " ";
return ostream;
}
// Utility functions
template <typename T>
void print(T &&t){
cout << t << "\n";
}
template <typename T, typename... Args>
void print(T &&t, Args &&... args){
cout << t << " ";
print(forward<Args>(args)...);
}
// Mathematical functions
int GCD(int a, int b)
{
while (b)
{
a %= b;
swap(a, b);
}
return a;
}
int GCD_extended(int a, int b, int &x, int &y)
{
x = 1, y = 0;
int x1 = 0, y1 = 1, a1 = a, b1 = b;
while (b1)
{
int q = a1 / b1;
tie(x, x1) = make_tuple(x1, x - q * x1);
tie(y, y1) = make_tuple(y1, y - q * y1);
tie(a1, b1) = make_tuple(b1, a1 - q * b1);
}
return a1;
}
int LCM(int a, int b)
{
return ((ll)a * b) / GCD(a, b);
}
ll modpow(ll x, ll n, int m = MOD)
{
if (x == 0 && n == 0) return 0; // undefined case
ll res = 1;
while (n > 0)
{
if (n % 2)
res = (res * x) % m;
x = (x * x) % m;
n /= 2;
}
return res;
}
int modinv(int x, int m = MOD)
{
return modpow(x, m - 2, m);
}
mt19937 rng;
int getRandomNumber(int l, int r)
{
uniform_int_distribution<int> dist(l, r);
return dist(rng);
}
/********************************************************
Main code starts here!
| ___ ___ . .
|.===. /\#/\ .|||. . .:::.
{}o o{} /(o o)\ (o o) :(o o): .
ooO--(_)--Ooo-ooO--(_)--Ooo-ooO--(_)--Ooo-ooO--(_)--Ooo-
********************************************************/
void pre() {
}
void solve(int tc) {
ll n; cin >> n;
vll a(n); cin >> a;
map<ll,ll> mp;
for0(i,n) mp[a[i]]++;
ll start = 1;
map<ll,pair<ll,ll>> f;
vll res(n, -1);
for0(i,n){
if(mp[a[i]]%a[i] != 0){
print("-1"); return;
}
if(f[a[i]].S > 0){
f[a[i]].S--;
}
else {
f[a[i]] = {start++, a[i]-1};
}
res[i] = f[a[i]].F;
}
print(res);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cout << setprecision(12) << fixed;
pre();
int tests = 1;
cin >> tests;
for (int tt = 1; tt <= tests; tt++)
solve(tt);
return 0;
}Frequency Array Retrieval CodeChef Solution in C++14
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define pb push_back
typedef long long ll;
#define int long long
#define ld long double
#define f(i,n) for(ll i=0;i<n;i++)
#define fo(i,a,b) for(ll i=a;i<=b;i++)
#define forr(i,a,b) for(ll i=a;i>=b;i--)
#define ee endl
#define mem(a,b) memset(a,b,sizeof(a))
#define bp __builtin_popcount
#define all(x) (x).begin(),(x).end()
#define s(x) sort(all(x))
#define r(x) reverse(all(x))
#define sz size()
#define ln length()
#define mod 1000000007
#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN
#define pb push_back
#define pf push_front
#define mp make_pair
#define F first
#define S second
#define mxe(v) *max_element(all(v))
#define vl vector<ll>
#define pll pair<ll,ll>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define precise(x) fixed << setprecision(x)
#define KHILADI ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL))
ll max(ll a , ll b){ if(a>b) return a; else return b;}
ll min(ll a , ll b){ if(a<b) return a; else return b;}
ll gcd(ll a,ll b){if(a==0)return b;return gcd(b%a,a);}
ll lcm(ll a,ll b){return (max(a,b)/gcd(a,b))*min(a,b);}
void solve(int ttt)
{
ll n;
cin >> n;
vl v(n);
unordered_map<int,pair<int,int>> m;
map<int,vector<int>> mp;
f(i,n){
cin >> v[i];
mp[v[i]].push_back(i);
}
for(auto i:mp){
if(i.second.size() % i.first != 0)
{
cout << -1 << '\n';
return;
}
}
vl ans(n,0);
int cnt = 1;
f(i,n){
if(m.find(v[i]) == m.end()){
ans[i] = cnt;
m[v[i]] = {cnt, 1};
cnt++;
}
else{
pair<int,int> p = m[v[i]];
if(p.second == v[i]){
ans[i] = cnt;
m[v[i]] = {cnt,1};
cnt++;
}
else{
ans[i] = p.first;
m[v[i]] = {p.first, p.second + 1};
}
}
}
f(i,n)
cout << ans[i] << ' ';
cout << '\n';
}
signed main()
{
KHILADI;
ll test_case=1;
cin >> test_case;
fo(ttt,1,test_case)
{
solve(ttt);
}
return 0;
}Frequency Array Retrieval CodeChef Solution in PYTH 3
# cook your dish here
t=int(input())
for i in range(t):
n=int(input())
B=[int(j) for j in input().split()]
u={}
k=1
for j in range(n):
if B[j] not in u:
u[B[j]]=[1,k]
k+=1
else:
if u[B[j]][0]%B[j]==0:
u[B[j]].append(k)
k+=1
u[B[j]][0]+=1
b=True
for j in u:
if u[j][0]%j!=0:
b=False
break
if b:
k=1
for j in B:
print(u[j][1],end=" ")
u[j][0]-=1
if u[j][0]%j==0:
u[j].pop(1)
print()
else:
print(-1)
Frequency Array Retrieval CodeChef Solution in C
#include <stdio.h>
int main(void) {
// your code goes here
int t;
scanf("%d",&t);
while(t-->0)
{
int n;
scanf("%d",&n);
if(n>0){
int a[n];
int b[n];
for(int i=0;i<n;i++)
{
scanf("%d",&b[i]);
a[i]=0;
}
int m=0;
int val=1;
for(int i=0;i<n;i++)
{
if(b[i]>n||b[i]<1)
m=1;
}
for(int i=0;i<n&&m==0;i++)
{
int count=0,v=0;
if(a[i]==0){
for(int j=i;j<n&&count<b[i];j++)
{
if(b[j]==b[i])
{
count++;
a[j]=val;
v=1;
}
}
}
if(v==1)
{
val++;
if(count!=b[i])
m=1;
}
}
if(m==0)
{
for(int i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
}
else
{
printf("-1\n");
}
}
}
return 0;
}
Frequency Array Retrieval CodeChef Solution in JAVA
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
// import java.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n=sc.nextInt();
int arr[]=new int[n];
HashMap<Integer,Integer> map=new HashMap<>();
for (int i = 0; i <n ; i++) {
arr[i]=sc.nextInt();
map.put(arr[i],map.getOrDefault(arr[i],0)+1);
}
boolean poss=true;
for(int k:map.keySet())
{
int val=map.get(k);
if(val%k!=0) {
poss = false;
break;
}
}
if(!poss)
{
System.out.println(-1);
continue;
}
map.clear();
int ans[]=new int[n];
int val[]=new int[n+1];
int cmax=0;
for (int i = 0; i <n ; i++) {
int num=arr[i];
if(map.containsKey(num))
{
if(map.get(num)==num)
{
cmax++;
val[num]=cmax;
map.put(num,1);
ans[i]=cmax;
}else{
map.put(num,map.get(num)+1);
ans[i]=val[num];
}
}else{
cmax++;
map.put(num,1);
ans[i]=cmax;
val[num]=cmax;
}
}
StringBuilder st=new StringBuilder();
for (int i = 0; i < n; i++) {
st.append(ans[i]+" ");
}
System.out.println(st.toString());
}
}
}Frequency Array Retrieval CodeChef Solution in PYPY 3
# watchu lookin at?
import sys
from math import *
# from itertools import *
# from heapq import heapify, heappop, heappush
# from bisect import bisect, bisect_left, bisect_right
from collections import deque, Counter, defaultdict as dd
mod = 10**9+7
abc = "abcdefghijklmnopqrstuvwxyz"
# Sangeeta Singh
def input(): return sys.stdin.readline().rstrip("\r\n")
def ri(): return int(input())
def rl(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def isPowerOfTwo(x): return (x and (not(x & (x - 1))))
def lcm(x, y): return (x*y)//gcd(x, y)
def alpha(x): return ord(x)-ord('A')
def gcd(x, y):
while y:
x, y = y, x % y
return x
def d2b(n):
s = bin(n).replace("0b", "")
return (34-len(s))*'0'+s
def highestPowerof2(x):
x |= x >> 1
x |= x >> 2
x |= x >> 4
x |= x >> 8
x |= x >> 16
return x ^ (x >> 1)
def nextPowerOf2(N):
if not (N & (N - 1)):
return N
return int("1" + (len(bin(N)) - 2) * "0", 2)
def isPrime(x):
if x == 1:
return False
if x == 2:
return True
for i in range(2, int(x ** 0.5) + 1):
if x % i == 0:
return False
return True
def factors(n):
i = 1
ans = []
while i <= sqrt(n):
if (n % i == 0):
if (n / i != i):
ans.append(int(n/i))
if i != 1:
ans.append(i)
i += 1
return ans
Primes = [1] * 100001
primeNos = []
def SieveOfEratosthenes(n):
p = 2
while (p * p <= n):
if (Primes[p]):
for i in range(p * p, n+1, p):
Primes[i] = 0
p += 1
for p in range(2, n+1):
if Primes[p]:
primeNos.append(p)
# SieveOfEratosthenes(100000)
# P = len(primeNos)
# print("P", P)
def ncr(n, r):
ans = 1
while(r):
ans *= n
ans %= mod
n -= 1
r -= 1
return ans
############ Main! #############
# mod = 998244353
def sangee():
n = ri()
b = rl()
a = []
d = dd(lambda: [0, 0])
f = 1
for i in range(n):
v = b[i]
if d[v][0] == 0:
d[v][0] = f
a.append(f)
f += 1
d[v][1] += 1
if d[v][1] >= v:
d[v][1] = 0
d[v][0] = 0
else:
d[v][1] += 1
a.append(d[v][0])
if d[v][1] >= v:
d[v][1] = 0
d[v][0] = 0
for i in d:
if d[i][0] != 0:
print(-1)
return
print(*a)
t = ri()
for _ in range(t):
sangee()Frequency Array Retrieval CodeChef Solution in C#
using System;
using System.Linq;
using System.Text;
public class Test
{
public static void Main()
{
var tests = int.Parse(Console.ReadLine());
for(var test = 0; test < tests; test++)
{
//var ar = Console.ReadLine().Split().Select(t => int.Parse(t)).ToArray();
var n = int.Parse(Console.ReadLine());
var indexArray = Console.ReadLine().Split().Select(t => int.Parse(t)).ToArray();
Tup[] vals = new Tup[n + 1]; // num vs frequency
var current = 0;
bool isCorrectInput = true;
var sb = new StringBuilder();
for (var i = 0; i < indexArray.Length; i++)
{
var ind = indexArray[i];
if(ind > n)
{
isCorrectInput = false;
break;
}
if (vals[ind].originalF != indexArray[i])
{
current++;
vals[ind] = new Tup(current, indexArray[i]);
}
if (vals[ind].originalF == indexArray[i] && vals[ind].remainingF == 0)
{
current++;
vals[ind] = new Tup(current, indexArray[i]);
}
vals[ind].remainingF -= 1;
sb.Append(vals[ind].num.ToString() + " ");
}
if (!isCorrectInput || vals.Where(c => c.remainingF > 0).Any())
Console.WriteLine(-1);
else
Console.WriteLine(sb.ToString().Trim());
}
}
private struct Tup
{
public Tup(int n, int f)
{
num = n;
originalF = f;
remainingF = f;
}
public int num;
public int remainingF;
public int originalF;
}
}Frequency Array Retrieval CodeChef Solution in NODEJS
process.stdin.resume();
process.stdin.setEncoding('utf8');
// declare global variables
var input_stdin = "";
// standard input is stored into input_stdin
process.stdin.on('data', function (data) {
input_stdin += data;
});
// standard input is done and stored into an array
process.stdin.on('end', function () {
chunks = input_stdin.split("\n");
main(chunks);
});
function main(data) {
let i = 0;
let t = Number(data[i++]);
while(t--) {
const n = Number(data[i++]);
const b = data[i++].split(" ");
solve(b);
}
}
function solve(b) {
const map = {};
let x = 1;
b = b.map((i) => {
let y;
i = Number(i);
if (map[i]) {
y = map[i].value;
map[i].freq--;
if (!map[i].freq) {
delete map[i];
}
} else {
y = x++;
if (i > 1) {
map[i] = {
value: x - 1,
freq: i - 1
}
}
}
return y;
});
if (Object.keys(map).length) {
console.log(-1);
} else {
console.log(b.join(' '));
}
}Frequency Array Retrieval CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
var buf bytes.Buffer
tc := readNum(reader)
for tc > 0 {
tc--
n := readNum(reader)
A := readNNums(reader, n)
res := solve(A)
if len(res) == 0 {
buf.WriteString("-1")
} else {
for i := 0; i < n; i++ {
buf.WriteString(fmt.Sprintf("%d ", res[i]))
}
}
buf.WriteByte('\n')
}
fmt.Print(buf.String())
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' || s[i] == '\r' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
var primes []int
var lpf []int
const MAX_A = 1000010
func init() {
lpf = make([]int, MAX_A)
for i := 2; i < MAX_A; i++ {
if lpf[i] == 0 {
primes = append(primes, i)
for j := i; j < MAX_A; j += i {
if lpf[j] == 0 {
lpf[j] = i
}
}
}
}
}
func solve(B []int) []int {
n := len(B)
//
// B[0] = x, A[0]
pos := make(map[int][]int)
id := make(map[int]int)
addFreq := func(f int, i int) {
if pos[f] == nil {
pos[f] = make([]int, 0, 1)
}
pos[f] = append(pos[f], i)
}
for i, f := range B {
addFreq(f, i)
}
A := make([]int, n)
num := 1
for i := 0; i < n; i++ {
if A[i] > 0 {
continue
}
f := B[i]
cnt := f
v := pos[f]
for id[f] < len(v) && cnt > 0 {
A[v[id[f]]] = num
id[f]++
cnt--
}
if cnt > 0 {
return nil
}
num++
}
for i := 0; i < n; i++ {
if A[i] == 0 {
return nil
}
}
return A
}Frequency Array Retrieval CodeChef Solution Review:
In our experience, we suggest you solve this Frequency Array Retrieval CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Frequency Array Retrieval CodeChef Solution.
Conclusion:
I hope this Frequency Array Retrieval CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
