Submission #315331

#TimeUsernameProblemLanguageResultExecution timeMemory
315331Kevin_Zhang_TWCat (info1cup19_cat)C++17
15 / 100
347 ms3400 KiB
#include<bits/stdc++.h> #define pb emplace_back #define AI(i) begin(i), end(i) using namespace std; using ll = long long; #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] = ", args) void kout() {cerr << endl;} template<class T1, class ...T2> void kout (T1 v, T2 ...e) { cerr << v << ' ', kout(e...); } template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; } #else #define DE(...) 0 #define debug(...) 0 #endif const int MAX_N = 300010; int n; vector<pair<int,int>> op; // just the front half void swap_sort(vector<int> p) { } bool valid(vector<int> p) { int cnt = 0, m = n / 2; for (int l = 0, r = n-1;l < r;++l, --r) { if ((p[l]>m) ^ (p[r]<=m)) return false; if (p[l] > m) ++cnt; } if (cnt & 1) return false; vector<int> ln, rn; for (int i = 0;i < m;++i) if (p[i] > m) ln.pb(i); for (int i = n-1;i >= m;--i) if (p[i] <= m) rn.pb(i); assert(cnt == ln.size() && cnt == rn.size()); vector<int> pos(n+1); for (int i = 0;i < n;++i) pos[ p[i] ] = i; auto sw = [&](int x, int y) { swap(p[x], p[y]), swap(pos[ p[x] ], pos[ p[y] ]); }; auto do_op = [&](int x, int y) { DE(x, y); int a = x, b = y, c = n - x - 1, d = n - y - 1; sw(a, b), sw(c, d); }; for (int i = 0;i < cnt;i += 2) do_op(ln[i], rn[i+1]); for (int i = 0;i < m;++i) { debug(AI(p)); while (i+1 != p[i]) { do_op(i, pos[i+1]); } } for (int i = 0;i < n;++i) if (p[i] != i+1) return false; return true; } // make p good enough so that I can do swap sort on it void pair_good(vector<int> &p) { } bool solve() { cin >> n; vector<int> p(n); for (int &i : p) cin >> i; if (!valid(p)) return false; pair_good(p); swap_sort(p); return true; } signed main() { ios_base::sync_with_stdio(0), cin.tie(0); int T; cin >> T; while (T--) { op.clear(); if (!solve()) cout << -1 << '\n'; else { cout << op.size() << ' ' << op.size() << '\n'; for (auto [a, b] : op) cout << a+1 << ' ' << b+1 << '\n'; } } }

Compilation message (stderr)

In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from cat.cpp:1:
cat.cpp: In function 'bool valid(std::vector<int>)':
cat.cpp:41:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  assert(cnt == ln.size() && cnt == rn.size());
      |         ~~~~^~~~~~~~~~~~
cat.cpp:41:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  assert(cnt == ln.size() && cnt == rn.size());
      |                             ~~~~^~~~~~~~~~~~
cat.cpp: In lambda function:
cat.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cat.cpp:49:3: note: in expansion of macro 'DE'
   49 |   DE(x, y);
      |   ^~
cat.cpp: In function 'bool valid(std::vector<int>)':
cat.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
cat.cpp:57:3: note: in expansion of macro 'debug'
   57 |   debug(AI(p));
      |   ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...