oj.uz

Submission #372890

# Submission time Handle Problem Language Result Execution time Memory
372890 2021-03-02T08:04:31 Z Traduttore Xor Sort (eJOI20_xorsort) C++14
60 / 100
 1000 ms 24920 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define pll pair <ll,ll>
#define F first
#define S second
#define int ll
#define pb push_back
#define IOS ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
using namespace __gnu_pbds;
typedef tree <pll,null_type,less <pll>,rb_tree_tag,tree_order_statistics_node_update> orduk;
typedef tree <ll,null_type,less <ll>,rb_tree_tag,tree_order_statistics_node_update> orduk2;
ll n,type;
vector <ll> a;
inline void init() {
    cin>>n>>type;
    a.resize(n);
    for (int i = 0;i < n;i++)
        cin>>a[i];
}
vector <pll> ans;
inline void output() {
    cout<<ans.size()<<'\n';
    for (auto to:ans)
        cout<<to.F<<" "<<to.S<<'\n';
    exit(0);
}
inline void solve() {
	int mn = 2e9;
	vector <pll> ans2;
	for (int i = 0;i < n - 1;i++)
	a[i]^=a[i + 1];
	for (int j = 0;j < n;j++) {
		vector <int> aa;
		aa = a;
	for (int i = 0;i < n;i++)
	if (i != j) a[i]^=a[j];
	ans.clear();
	vector <int> ab;
	ab = aa;
	for (int i = 0;i < n - 1;i++)
	ans.pb({i + 1,i + 2});
	for (int i = j + 1;i < n;i++)
	{
		ans.pb({i + 1,i});
		ab[i]^=ab[i - 1];
	}
	for (int i = j - 1;i >= 0;i--)
	{
		ans.pb({i + 1,i + 2});
		ab[i]^=ab[i + 1];
	}
	a = ab;
	if (type == 1) {
	unordered_map <int,int> mp;
	bool YY = true;
	for (int i = 0;i < n;i++)
	{
		if (mp[a[i]]) {YY = false;break;}
		++mp[a[i]];
	}
	if (YY == false) {
		a = aa;
		continue;
	}
	}
    while (1) {
        bool found = true;
        int mx = -1;
        int pos = -1;
        for (int i = 0;i < n - 1;i++)
        if (a[i] > a[i + 1]) {
        	pos = i;
        	break;
        }
        if (pos < 0) break;
            ans.pb({pos + 2,pos + 1});
            ans.pb({pos + 1, pos + 2});
            ans.pb({pos + 2,pos + 1});
            swap(a[pos],a[pos + 1]);
    }
    if (ans.size() < mn) {
    	mn = ans.size();
    	ans2 = ans;
    }
    a = aa;
}
ans = ans2;
}
 
int32_t main() {
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
IOS;
int m;
m = 10;
m-=9;
while (m--)
{
    init();
    solve();
    output();
}
}
/*written by Traduttore*/
/*waiting for a miracle...*/

Compilation message

xorsort.cpp: In function 'void solve()':
xorsort.cpp:71:14: warning: unused variable 'found' [-Wunused-variable]
   71 |         bool found = true;
      |              ^~~~~
xorsort.cpp:72:13: warning: unused variable 'mx' [-Wunused-variable]
   72 |         int mx = -1;
      |             ^~
xorsort.cpp:85:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   85 |     if (ans.size() < mn) {
      |         ~~~~~~~~~~~^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 496 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 91 ms 1276 KB Output is correct
5 Correct 88 ms 1020 KB Output is correct
6 Correct 89 ms 1020 KB Output is correct
7 Correct 83 ms 1020 KB Output is correct
8 Correct 102 ms 1020 KB Output is correct
9 Correct 105 ms 1168 KB Output is correct
10 Correct 96 ms 1020 KB Output is correct
11 Correct 73 ms 1088 KB Output is correct
12 Correct 87 ms 1532 KB Output is correct
13 Correct 78 ms 1528 KB Output is correct
14 Correct 87 ms 1524 KB Output is correct
15 Correct 74 ms 1528 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 496 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 91 ms 1276 KB Output is correct
5 Correct 88 ms 1020 KB Output is correct
6 Correct 89 ms 1020 KB Output is correct
7 Correct 83 ms 1020 KB Output is correct
8 Correct 102 ms 1020 KB Output is correct
9 Correct 105 ms 1168 KB Output is correct
10 Correct 96 ms 1020 KB Output is correct
11 Correct 73 ms 1088 KB Output is correct
12 Correct 87 ms 1532 KB Output is correct
13 Correct 78 ms 1528 KB Output is correct
14 Correct 87 ms 1524 KB Output is correct
15 Correct 74 ms 1528 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 87 ms 1276 KB Output is correct
18 Correct 242 ms 1656 KB Output is correct
19 Correct 258 ms 2040 KB Output is correct
20 Correct 249 ms 2040 KB Output is correct
21 Correct 253 ms 1528 KB Output is correct
22 Correct 251 ms 1528 KB Output is correct
23 Correct 248 ms 2060 KB Output is correct
24 Correct 239 ms 2168 KB Output is correct
25 Correct 240 ms 1656 KB Output is correct
26 Correct 238 ms 1544 KB Output is correct
27 Correct 240 ms 1536 KB Output is correct
28 Correct 238 ms 1576 KB Output is correct
29 Correct 237 ms 1552 KB Output is correct
30 Correct 239 ms 1544 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 236 ms 1388 KB Output is correct
5 Execution timed out 1078 ms 24920 KB Time limit exceeded
6 Halted 0 ms 0 KB -