Submission #524567

#	Time	Username	Problem	Language	Result	Execution time	Memory
524567		cqtshadow	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1089 ms	2624 KiB

shoes

#include <bits/stdc++.h>
#define MASK(x) (1LL << x)
#define GETBIT(mask, x) ((mask >> (x))&1)
#define ONBIT(mask, x) (mask | (1LL << (x)))
#define Each(type, i, a, b) for(type i = (a) ; i <= (b) ; ++i)
#define REach(type, i, a, b) for(type i = (a) ; i >= (b) ; --i)
using namespace std;

typedef long long ll;

const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 2e9;
const double eps = 1e-9;
const ll oo = 4e18;

template<class X> bool maximize(X &x, X y) {return (x + eps < y ? x = y, true : false);}
template<class X> bool minimize(X &x, X y) {return (x > y + eps ? x = y, true : false);}

void add(int &x, int y) {x += y; if(x >= MOD) x -= MOD;}
void sub(int &x, int y) {x -= y; if(x < 0) x += MOD;}
int radd(int x, int y) {add(x, y); return x;}
int rsub(int x, int y) {sub(x, y); return x;}

string to2(int val) {bitset<10> temp(val); return temp.to_string();}

int n;

namespace SUB1 {
    ll solve(vector<int> S) {
        return S[0] > S[1];
    }
}

namespace SUB5 {
    bitset<2002> Marked;

    ll solve(vector<int> S) {
        ll ans = 0;
        Each(int, i, 0, 2*n - 1) if(Marked[i] == 0) {
            int need = -S[i];
            int pos = i + 1;
            int sum = 0;
            while(true) {
                if(Marked[pos]) {++pos; continue;}
                if(S[pos] != need) {++sum; ++pos; continue;}
                break;
            }
            ans += sum + (S[i] > 0);
            Marked[pos] = 1;
        }
        return ans;
    }
}

ll count_swaps(vector<int> S) {
    n = S.size()/2;

    if(n == 1) return SUB1::solve(S);

    if(n <= 1000) return SUB5::solve(S);
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15