oj.uz

Submission #372893

# Submission time Handle Problem Language Result Execution time Memory
372893 2021-03-02T08:08:19 Z Traduttore Xor Sort (eJOI20_xorsort) C++14
60 / 100
 1000 ms 23604 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 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 = 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;
	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:65:14: warning: unused variable 'found' [-Wunused-variable]
   65 |         bool found = true;
      |              ^~~~~
xorsort.cpp:66:13: warning: unused variable 'mx' [-Wunused-variable]
   66 |         int mx = -1;
      |             ^~
xorsort.cpp:79: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]
   79 |     if (ans.size() < mn) {
      |         ~~~~~~~~~~~^~~~

Subtask #1
25.0 / 25.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 68 ms 1012 KB Output is correct
5 Correct 70 ms 1268 KB Output is correct
6 Correct 70 ms 1012 KB Output is correct
7 Correct 69 ms 1012 KB Output is correct
8 Correct 69 ms 1268 KB Output is correct
9 Correct 71 ms 1012 KB Output is correct
10 Correct 69 ms 1012 KB Output is correct
11 Correct 66 ms 1140 KB Output is correct
12 Correct 87 ms 1136 KB Output is correct
13 Correct 74 ms 1136 KB Output is correct
14 Correct 79 ms 1264 KB Output is correct
15 Correct 77 ms 1136 KB Output is correct

Subtask #2
35.0 / 35.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 68 ms 1012 KB Output is correct
5 Correct 70 ms 1268 KB Output is correct
6 Correct 70 ms 1012 KB Output is correct
7 Correct 69 ms 1012 KB Output is correct
8 Correct 69 ms 1268 KB Output is correct
9 Correct 71 ms 1012 KB Output is correct
10 Correct 69 ms 1012 KB Output is correct
11 Correct 66 ms 1140 KB Output is correct
12 Correct 87 ms 1136 KB Output is correct
13 Correct 74 ms 1136 KB Output is correct
14 Correct 79 ms 1264 KB Output is correct
15 Correct 77 ms 1136 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 69 ms 1012 KB Output is correct
18 Correct 248 ms 1904 KB Output is correct
19 Correct 194 ms 1540 KB Output is correct
20 Correct 200 ms 2032 KB Output is correct
21 Correct 193 ms 2040 KB Output is correct
22 Correct 195 ms 1648 KB Output is correct
23 Correct 208 ms 1520 KB Output is correct
24 Correct 195 ms 2032 KB Output is correct
25 Correct 195 ms 1648 KB Output is correct
26 Correct 228 ms 1772 KB Output is correct
27 Correct 210 ms 1772 KB Output is correct
28 Correct 226 ms 2032 KB Output is correct
29 Correct 220 ms 1772 KB Output is correct
30 Correct 221 ms 1828 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 3 ms 492 KB Output is correct
4 Correct 217 ms 2032 KB Output is correct
5 Execution timed out 1047 ms 23604 KB Time limit exceeded
6 Halted 0 ms 0 KB -