oj.uz

Submission #315340

# Submission time Handle Problem Language Result Execution time Memory
315340 2020-10-22T14:24:48 Z Kevin_Zhang_TW Cat (info1cup19_cat) C++17
15 / 100
 502 ms 7800 KB 
#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) {
	vector<int> pos(n+1);
	int m = n/2;
	for (int i = 0; i < n;++i)
		pos[ p[i] ] = i;
	auto sw = [&](int x, int y) {
		op.pb(x, y);
		swap(p[x], p[y]), swap(pos[p[x]], pos[p[y]]);
	};
	return;
	for (int i = 0;i < m;++i) {
		while (i+1 != p[i]) 
			sw(i, pos[i]);
	}
}
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;
	DE(cnt);
	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) {
		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) {
		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
vector<int> pair_good(vector<int> p) {
	vector<int> notp;
	vector<int> pos(n+1);
	vector<int> goodp(p);
	cerr << "Pair_good\n";
	debug(AI(p));
	auto put = [&](int id) {
		DE(id);
		notp.pb(id);
	};
	auto sw = [&](int a, int b) {
		swap(p[a], p[b]), swap(pos[ p[a] ], pos[ p[b] ]);
	};
	auto do_op = [&](int x, int y) {
		DE(x, y);
		int a = x, b = y, c = n - a - 1, d = n - b - 1;
		swap( goodp[a], goodp[b] );
		swap( goodp[c], goodp[d] );
		op.pb(a, b);
	};
		
	auto pop = [&]() {
		while (notp.size() > 1) {
			int a = notp.back(); notp.pop_back();
			int b = notp.back(); notp.pop_back();
			do_op(a, n-b-1);
		}
	};
	int m = n / 2;
	vector<bool> ch(n), vis(n);
	int cnt = 0;
	for (int i = 0;i < m;++i)
		if (p[i] > m)
			swap(p[i], p[n-i-1]), ch[i] = true, ++cnt;


	for (int i = 0;i < m;++i) 
		pos[p[i]] = i;

	DE(cnt);
	debug(AI(p));
	for (int i = 0;i < m;++i) {
		if (vis[i]) continue;
		vis[i] = true;
		if (ch[i])
			put(i);
			
		while (i+1 != p[i]) {
			int x = p[i]-1;
			if (ch[x])
				put(x);

			vis[x] = true;
			sw(i, x);
		}
		pop();
	}
	assert(notp.empty());
	cerr << "Good P\n";
	debug(AI(goodp));
	return goodp;
}
bool solve() {
	cin >> n;
	vector<int> p(n);
	for (int &i : p)
		cin >> i;
	debug(AI(p));
	if (!valid(p))
		return false;
	p = 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

cat.cpp: In function 'bool valid(std::vector<int>)':
cat.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cat.cpp:46:2: note: in expansion of macro 'DE'
   46 |  DE(cnt);
      |  ^~
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:55:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  assert(cnt == ln.size() && cnt == rn.size());
      |         ~~~~^~~~~~~~~~~~
cat.cpp:55:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  assert(cnt == ln.size() && cnt == rn.size());
      |                             ~~~~^~~~~~~~~~~~
cat.cpp: In function 'std::vector<int> pair_good(std::vector<int>)':
cat.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
cat.cpp:85:2: note: in expansion of macro 'debug'
   85 |  debug(AI(p));
      |  ^~~~~
cat.cpp: In lambda function:
cat.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cat.cpp:87:3: note: in expansion of macro 'DE'
   87 |   DE(id);
      |   ^~
cat.cpp: In lambda function:
cat.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cat.cpp:94:3: note: in expansion of macro 'DE'
   94 |   DE(x, y);
      |   ^~
cat.cpp: In function 'std::vector<int> pair_good(std::vector<int>)':
cat.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
cat.cpp:119:2: note: in expansion of macro 'DE'
  119 |  DE(cnt);
      |  ^~
cat.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
cat.cpp:120:2: note: in expansion of macro 'debug'
  120 |  debug(AI(p));
      |  ^~~~~
cat.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
cat.cpp:139:2: note: in expansion of macro 'debug'
  139 |  debug(AI(goodp));
      |  ^~~~~
cat.cpp: In function 'bool solve()':
cat.cpp:15:20: warning: statement has no effect [-Wunused-value]
   15 | #define debug(...) 0
      |                    ^
cat.cpp:147:2: note: in expansion of macro 'debug'
  147 |  debug(AI(p));
      |  ^~~~~

Subtask #1
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 512 KB Correctly distinguished between possibility and impossibility

Subtask #2
1.5 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 640 KB Correctly distinguished between possibility and impossibility
2 Correct 45 ms 640 KB Correctly distinguished between possibility and impossibility

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 512 KB Correctly distinguished between possibility and impossibility
2 Correct 45 ms 640 KB Correctly distinguished between possibility and impossibility
3 Correct 45 ms 640 KB Correctly distinguished between possibility and impossibility
4 Correct 52 ms 760 KB Correctly distinguished between possibility and impossibility
5 Correct 21 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 19 ms 512 KB Correctly distinguished between possibility and impossibility

Subtask #4
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 640 KB Correctly distinguished between possibility and impossibility
2 Correct 45 ms 640 KB Correctly distinguished between possibility and impossibility
3 Correct 362 ms 2228 KB Correctly distinguished between possibility and impossibility
4 Correct 364 ms 2904 KB Correctly distinguished between possibility and impossibility
5 Correct 403 ms 3480 KB Correctly distinguished between possibility and impossibility

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 512 KB Correctly distinguished between possibility and impossibility
2 Correct 45 ms 640 KB Correctly distinguished between possibility and impossibility
3 Correct 45 ms 640 KB Correctly distinguished between possibility and impossibility
4 Correct 52 ms 760 KB Correctly distinguished between possibility and impossibility
5 Correct 21 ms 512 KB Correctly distinguished between possibility and impossibility
6 Correct 19 ms 512 KB Correctly distinguished between possibility and impossibility
7 Correct 362 ms 2228 KB Correctly distinguished between possibility and impossibility
8 Correct 364 ms 2904 KB Correctly distinguished between possibility and impossibility
9 Correct 403 ms 3480 KB Correctly distinguished between possibility and impossibility
10 Correct 480 ms 4704 KB Correctly distinguished between possibility and impossibility
11 Correct 446 ms 4176 KB Correctly distinguished between possibility and impossibility
12 Correct 416 ms 6284 KB Correctly distinguished between possibility and impossibility
13 Correct 502 ms 7800 KB Correctly distinguished between possibility and impossibility
14 Correct 431 ms 6520 KB Correctly distinguished between possibility and impossibility