oj.uz

Submission #433801

# Submission time Handle Problem Language Result Execution time Memory
433801 2021-06-20T10:56:25 Z hhhhaura Permutation Recovery (info1cup17_permutation) C++14
Compilation error
 0 ms 0 KB 
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 1000000000000000000
#define eps (1e-9)

using namespace std;

#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a) 
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace solver {
	random;
	int n, sz, bk;
	int mod = abs(rnd() * rnd());
	vector<int> a, tag, vis, ans;
	vector<pii> b;
	void init_(int _n) {
		n = _n, sz = sqrt(n) + 1, bk = ceil(n, sz);
		a.assign(n + 1, 0);
		tag.assign(bk + 1, 0);
		vis.assign(n + 1, 0);
		ans.assign(n + 1, 0);
		b.assign(n + 1, {0, 0});	
	}
	void build(int id) {
		int l = (id - 1) * sz + 1, r = min(n, id * sz);
		rep(i, l, r) {
			pii cur = b[i];
			if(vis[cur.second]) b[i] = {-1, cur.second};
			else b[i] = {(cur.first + tag[id] + MOD) % MOD, cur.second};
		}
		tag[id] = 0;
		sort(b.begin() + l, b.begin() + r + 1);
		return;
	} 
	int get_int(string s) {
		int ans = 0;
		for(auto i : s) ans = (ans * 10 + i - '0') % MOD;
		return ans;
	}
	int query() {
		rrep(i, 1, bk) {
			int l = (i - 1) * sz + 1, r = min(n, i * sz);
			int val = (1 - tag[i] + MOD) % MOD;
			int id = upper_bound(b.begin() + l, b.begin() + r + 1, pii(val, INF)) - b.begin() - 1;
			if(id <= r && id >= l && b[id].first == val) return b[id].second;
		}
		return -1;
	}
	void modify(int st, int val) {
		int id = ceil(st, sz);
		rep(i, (id - 1) * sz + 1, id * sz) {
			if(b[i].second >= st) b[i].first = (val + b[i].first) % MOD;
		}
		build(id);
		rep(i, ceil(st, sz) + 1, bk) tag[i] = (tag[i] + val) % MOD;
	} 
	void solve() {
		rrep(i, 1, n) {
			a[i] = (a[i] - a[i - 1] + MOD) % MOD;
			b[i] = {a[i], i};
		}
		rep(i, 1, bk) build(i);
		rep(i, 1, n) {
			int cur = query();
			ans[cur] = i, vis[cur] = 1;
			modify(cur, MOD - a[cur]);
		}
		rep(i, 1, n) cout << ans[i] << " \n"[i == n];
	}
};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n; cin >> n;
	init_(n);
	rep(i, 1, n) {
		string s; cin >> s;
		a[i] = get_int(s);
	}
	solve();
	return 0;
}

Compilation message

permutation.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
permutation.cpp:23:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
permutation.cpp:23:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~
permutation.cpp:33:29: error: call of overloaded 'abs(std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type)' is ambiguous
   33 |  int mod = abs(rnd() * rnd());
      |                             ^
In file included from /usr/include/c++/10/bits/std_abs.h:38,
                 from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from permutation.cpp:2:
/usr/include/stdlib.h:840:12: note: candidate: 'int abs(int)'
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/10/cmath:47,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from permutation.cpp:2:
/usr/include/c++/10/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/10/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
permutation.cpp: In function 'void solver::build(long long int)':
permutation.cpp:49:40: error: 'MOD' was not declared in this scope
   49 |    else b[i] = {(cur.first + tag[id] + MOD) % MOD, cur.second};
      |                                        ^~~
permutation.cpp:49:62: error: no match for 'operator=' (operand types are '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'std::pair<long long int, long long int>'} and '<brace-enclosed initializer list>')
   49 |    else b[i] = {(cur.first + tag[id] + MOD) % MOD, cur.second};
      |                                                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from permutation.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<long long int, long long int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<long long int, long long int>&, const std::__nonesuch&>::type' {aka 'const std::pair<long long int, long long int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long long int; _T2 = long long int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<long long int, long long int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<long long int, long long int>&&, std::__nonesuch&&>::type' {aka 'std::pair<long long int, long long int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
permutation.cpp:49:62: note:   couldn't deduce template parameter '_U1'
   49 |    else b[i] = {(cur.first + tag[id] + MOD) % MOD, cur.second};
      |                                                              ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from permutation.cpp:2:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = long long int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
permutation.cpp:49:62: note:   couldn't deduce template parameter '_U1'
   49 |    else b[i] = {(cur.first + tag[id] + MOD) % MOD, cur.second};
      |                                                              ^
permutation.cpp: In function 'long long int solver::get_int(std::string)':
permutation.cpp:57:48: error: 'MOD' was not declared in this scope
   57 |   for(auto i : s) ans = (ans * 10 + i - '0') % MOD;
      |                                                ^~~
permutation.cpp: In function 'long long int solver::query()':
permutation.cpp:63:28: error: 'MOD' was not declared in this scope
   63 |    int val = (1 - tag[i] + MOD) % MOD;
      |                            ^~~
permutation.cpp: In function 'void solver::modify(long long int, long long int)':
permutation.cpp:72:60: error: 'MOD' was not declared in this scope
   72 |    if(b[i].second >= st) b[i].first = (val + b[i].first) % MOD;
      |                                                            ^~~
permutation.cpp:75:58: error: 'MOD' was not declared in this scope
   75 |   rep(i, ceil(st, sz) + 1, bk) tag[i] = (tag[i] + val) % MOD;
      |                                                          ^~~
permutation.cpp: In function 'void solver::solve()':
permutation.cpp:79:30: error: 'MOD' was not declared in this scope
   79 |    a[i] = (a[i] - a[i - 1] + MOD) % MOD;
      |                              ^~~
permutation.cpp:86:16: error: 'MOD' was not declared in this scope
   86 |    modify(cur, MOD - a[cur]);
      |                ^~~