General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
239141643 Practice:
streidi
1910H - 7 Kotlin 1.7 Compilation error 0 ms 0 KB 2023-12-28 02:44:50 2023-12-28 02:44:50
→ Source
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll, ll> prll;
typedef unordered_map<ll,ll> umapll;

#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define sz size
#define all(x) (x).begin(), (x).end()
#define all0(x) (x).begin(), ((x).begin()+n)
#define all1(x) ((x).begin()+1), ((x).begin()+n+1)
#define allrev(x) (x).rbegin(), (x).rend()
#define in(v,s) ((s).find((v)) != (s).end())
#define GCD(x,y) __gcd(abs((x)), abs((y)))

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
	#define eprintf(...) 42
#endif

#define mxN 200'010ll
#define INF (LLONG_MAX>>3ll)
#define MOD 1'000'000'007ll
#define LOG 9ll // maybe 8 ???? (prob not, 9)

inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }

ll n;
ll sums;
vcll ar(mxN);
vc<vcll> lists(LOG+5, vcll(mxN, INF));

vc<vcll> poses(LOG+5, vcll(mxN, -1));
vcll seq(mxN);

inline void input()
{
	scanf("%lli", &n);
	ll i;
	f0r(i,1,n) scanf("%lli", &ar[i]);
}

queue<ll> values[15];
inline void rsort (vcll &ar2, ll m)
{
	ll i, j;
	f0r(i,1,n)
	{
		ll v=ar2[i];
		j = (v%m) / (m/10);
		values[j].push(v);
	}
	ar2.clear(); ar2.pb({-1});

	f0r(j,0,9) while (values[j].sz())
	{
		ll v=values[j].front(); values[j].pop();
		ar2.pb(v);
	}
}

inline void build_lists()
{
	ll i, j;
	sums=0;
	ll m=1;
	f0r(i,1,n) lists[0][i]=ar[i];

	f0r(j,1,LOG)
	{
		m*=10;
		f0r(i,1,n) lists[j][i]=lists[j-1][i];
		rsort(lists[j], m); // linear time
		f0r(i,1,n) lists[j-1][i] %= (m/10);

		f0r(i,1,n) sums += (ar[i]%m) / (m/10);
	}
}

inline void donbs (vcll &ar2, vcll &out) // do n binary searches
{
	ll i1=1, i2=1; // i1 is for "seq", i2 is for "ar2"

	while (i1<=n)
	{
		if (seq[i1] <= ar2[i2]) out[i1++]=i2-1;
		else i2++;
	}
}

inline void build_poses() // we don't need ar anymore ?
{
	ll i, j;
	ll m=1;

	f0r(j,1,LOG)
	{
		m*=10;
		f0r(i,1,n) seq[i] = m-lists[j][i];
		reverse(all1(seq));

		ll i1, i2;
		donbs(lists[j], poses[j]); // "do n binary searches" // with seq // lower_bound()
		reverse(all1(poses[j]));
	}
}

inline ll qry (ll i)
{
	ll v=ar[i];
	ll j;
	ll m=1; // mod
	ll s=0;

	f0r(j,1,LOG)
	{
		m*=10;
		ll x=v%m;
		s+=n * (x / (m/10));
		x = m-x;

		ll k = poses[j][i];
		k = n-k;

		s -= k*9;
	}

	return s;
}

inline void queries()
{
	ll i;
	f0r(i,1,n)
	{
		ll ans = qry(i) + sums;
		printf("%lli%c", ans, i==n ? '\n' : ' ');
	}
}

int main()
{
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
	srand(time(0));

	// freopen("file.in", "r", stdin);
	// freopen("file.out", "w", stdout);

	input();
	build_lists(); // good
	build_poses();
	queries();

	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details