Submission #1186282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186282		vnedu	Xor Sort (eJOI20_xorsort)	C++17	0 / 100	0 ms	328 KiB

xorsort

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }

#define fi first
#define se second

#define pb push_back
#define ii pair<int, int>

#define all(x) x.begin(), x.end()

#define TASK "nonsense"

/// end of template ///

const int N = 1e3 + 10;
int n,a[N];
vector<ii> history;
void op(int i, int j)
{
    a[i]^=a[j];
    history.pb({i,j});
}
void work()
{
    cout<<(int)history.size()<<'\n';
    for(ii cm : history) cout<<cm.fi<<' '<<cm.se<<'\n';
}
namespace sub1
{
    void solve()
    {
        for(int pos=n;pos>=1;--pos)
        {
            for(int i=1;i<=pos;++i) if(i<n) op(i,i+1);
            int mx=INT_MIN,cm,sum=0;
            for(int i=pos;i>=1;--i) if(maximize(mx,sum^=a[i])) cm=i;
//            cout<<pos<<' '<<mx<<' '<<cm<<'\n';
            for(int i=cm+1;i<=pos;++i) op(i,i-1);
            for(int i=cm-2;i>=1;--i) op(i,i+1);
//            cout<<a[pos]<<'\n';
        }
        work();
//        for(int i=1;i<=n;++i) cout<<a[i]<<' ';
    }
}
namespace sub2
{
    void solve()
    {
        for(int i=n;i>=1;--i)
        {
            bool ok=0;
            for(int b=19;b>=0;--b)
            {
                for(int j=1;j<=n;++j) ok|=((a[j]>>b)&1);
                if(ok)
                {
                    for(int j=2;j<=i;++j) if((a[j-1]>>b)&1)
                    {
                        if(!((a[j]>>b)&1)) op(j,j-1);
                        op(j-1,j);
                    }
                    break;
                }
            }
            if(!ok) break;
        }
        work();
    }
}
void solve()
{
    int s;
    cin>>n>>s;
    for(int i=1;i<=n;++i) cin>>a[i];
//    if(s==1) return void(sub1::solve());
    if(s==2) return void(sub2::solve());
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);

    int testcase=1;
//    cin>>testcase;

    while (testcase--)
        solve();

    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40