Submission #433801

#TimeUsernameProblemLanguageResultExecution timeMemory
433801hhhhauraPermutation Recovery (info1cup17_permutation)C++14
Compilation error
0 ms0 KiB
#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 (stderr)

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]);
      |                ^~~