oj.uz

Submission #315331

# Submission time Handle Problem Language Result Execution time Memory
315331 2020-10-22T13:49:16 Z Kevin_Zhang_TW Cat (info1cup19_cat) C++17
15 / 100
 347 ms 3400 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) {
}
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

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

Subtask #1
2.25 / 15.0

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

Subtask #2
1.5 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 512 KB Correctly distinguished between possibility and impossibility
2 Correct 18 ms 416 KB Correctly distinguished between possibility and impossibility

Subtask #3
3.75 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Correctly distinguished between possibility and impossibility
2 Correct 17 ms 512 KB Correctly distinguished between possibility and impossibility
3 Correct 18 ms 416 KB Correctly distinguished between possibility and impossibility
4 Correct 21 ms 512 KB Correctly distinguished between possibility and impossibility
5 Correct 7 ms 384 KB Correctly distinguished between possibility and impossibility
6 Correct 7 ms 512 KB Correctly distinguished between possibility and impossibility

Subtask #4
2.25 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 512 KB Correctly distinguished between possibility and impossibility
2 Correct 18 ms 416 KB Correctly distinguished between possibility and impossibility
3 Correct 310 ms 1668 KB Correctly distinguished between possibility and impossibility
4 Correct 318 ms 2044 KB Correctly distinguished between possibility and impossibility
5 Correct 316 ms 3040 KB Correctly distinguished between possibility and impossibility

Subtask #5
5.25 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Correctly distinguished between possibility and impossibility
2 Correct 17 ms 512 KB Correctly distinguished between possibility and impossibility
3 Correct 18 ms 416 KB Correctly distinguished between possibility and impossibility
4 Correct 21 ms 512 KB Correctly distinguished between possibility and impossibility
5 Correct 7 ms 384 KB Correctly distinguished between possibility and impossibility
6 Correct 7 ms 512 KB Correctly distinguished between possibility and impossibility
7 Correct 310 ms 1668 KB Correctly distinguished between possibility and impossibility
8 Correct 318 ms 2044 KB Correctly distinguished between possibility and impossibility
9 Correct 316 ms 3040 KB Correctly distinguished between possibility and impossibility
10 Correct 347 ms 1008 KB Correctly distinguished between possibility and impossibility
11 Correct 314 ms 1172 KB Correctly distinguished between possibility and impossibility
12 Correct 321 ms 3272 KB Correctly distinguished between possibility and impossibility
13 Correct 346 ms 3220 KB Correctly distinguished between possibility and impossibility
14 Correct 324 ms 3400 KB Correctly distinguished between possibility and impossibility