﻿HDU 6098 Inversion-Ocrosoft

Inversion

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 130    Accepted Submission(s): 95

Problem Description
Give an array A, the index starts from 1.
Now we want to know Bi=maxi∤jAj , i≥2.

Input
The first line of the input gives the number of test cases T; T test cases follow.
Each case begins with one line with one integer n : the size of array A.
Next one line contains n integers, separated by space, ith number is Ai.
Limits
T≤20
2≤n≤100000
1≤Ai≤1000000000
∑n≤700000

Output
For each test case output one line contains n-1 integers, separated by space, ith number is Bi+1.

Sample Input

2
4
1 2 3 4
4
1 4 2 3



Sample Output

3 4 3
2 4 4



Solution
2017 Multi-University Training Contest – Team 6

#define C11
#include <set>
#include <map>
#include <stack>
#include <string>
#include <cstdio>
#include <queue>
#include <vector>
#include <cmath>
#include <climits>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <functional>
#ifdef C11
#include <tuple>
#include <regex>
#include <random>
#include <complex>
#endif
using namespace std;
/** const var def */
const double eps = 1e-8;
const int maxn = 1e5 + 10;
const int MAXN = maxn * 4;
const int MOD = 1000000007;
/** type def */
typedef long long LL;
typedef pair<int, int> Pii;
typedef pair<LL, LL> Pll;
typedef vector<int> Vi;
typedef pair<double, double> Vec2;
#ifdef C11
using Vec3 = tuple<double, double, double>;
using Tp3 = tuple<int, int, int>;
#endif
/** easy def */
#define ms(a) memset(a,0,sizeof(a))
#define msr(a) memset(a,-1,sizeof(a))
/* first, second, position */
#define _f first
#define _s second
#define _p(_tp,_pos) get<_pos>(_tp)
/* operator */
Pii operator +(const Pii &x, const Pii &y) { return Pii(x.first + y.first, x.second + y.second); }
Pii operator -(const Pii &x) { return Pii(-x.first, -x.second); }
Pii operator -(const Pii &x, const Pii &y) { return x + (-y); }
Pii operator +=(Pii &x, const Pii &y) { return x = x + y; }
Pii operator -=(Pii &x, const Pii &y) { return x = x - y; }
#pragma region input&output
{
char CH; bool F = false;
for (CH = getchar(); CH<'0' || CH>'9'; F = CH == '-', CH = getchar());
for (num = 0; CH >= '0'&&CH <= '9'; num = num * 10 + CH - '0', CH = getchar());
F && (num = -num);
return num;
}
{
T num;
}
#ifdef C11
template<class T, class... Args>inline int read(T &t, Args &...args)
{
return t;
}
#endif
template<class T> inline void print(T p, char ed = '\n')
{
int stk[70], tp = 0;
if (p < 0) { putchar('-'); p = -p; }
if (!p) { putchar('0'); if (ed != '\0')putchar(ed); return; }
while (p) stk[++tp] = p % 10, p /= 10;
while (tp) putchar(stk[tp--] + '0');
if (ed != '\0')putchar(ed);
}
#ifdef C11
template<class T, class... Args>inline void print(T t, Args ...args)
{
print(t, '\0');
if (sizeof...(args))putchar(' ');
else putchar('\n');
print(args...);
}
#endif
#pragma endregion

int main()
{
while (N--)
{
vector<Pii> vec(n);
set<int> s;
for (int i = 0; i < n; ++i)
{
if (i)s.insert(i + 1);
vec[i].second = i + 1;
}
sort(begin(vec), end(vec), greater<Pii>());
Vi ans(n + 1); //int cnt = 0;
for (auto each : vec)
{
int p = each.second;
for (auto it = begin(s); it != s.end();)
{
if (p%*it)
{
//++cnt;
ans[*it] = each.first;
it = s.erase(it);
//if (cnt == n - 1)break;
}
else ++it;
}
}
for (int i = 2; i <= n; i++)
printf("%d%s", ans[i], i == n ? "\n" : " ");
}
return 0;
}