제출 #1233670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233670		retr0foxx	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	203 ms	273644 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <deque>

/*
a certain segment...

*/

using haha = int;
#define int long long

#define printf

// #define MAXN 20
#define MAXN 200005

int fenwick[MAXN];
int fwlen;

void fwadd(int i, int x)
{
    ++i;
    if (i < 1) i = 1;
    if (i > fwlen) return;
    
    while (i <= fwlen)
    {
        fenwick[i] += x;
        i += i & (-i);
    }
}

int fwget(int i)
{
    ++i;
    if (i < 1) return 0;
    if (i > fwlen) i = fwlen;
    
    int result = 0;
    while (i >= 1)
    {
        result += fenwick[i];
        i -= i & (-i);
    }
    return result;
}

std::deque<int> stack_neg[MAXN];
std::deque<int> stack_pos[MAXN];

long long count_swaps(std::vector<haha> s) {
    printf("where is it breaking?\n");
    fwlen = s.size();
    
    int result = 0;
    for (int i = 0; i < s.size(); ++i)
    {
        printf("wat da hell\n");
        int current = s[i];
        int left = current < 0;
        current = std::abs(current);
        
        printf("Tree state is: ");
        for (int i = 0; i < s.size(); ++i) printf("%i ", fwget(i));
        printf("\n");
        if (left && stack_pos[current].size())
        {
            printf("negative %i in index %i got a pair in %i (%i)\n", current, i, stack_pos[current].front(), stack_pos[current].front() + fwget(stack_pos[current].front()));
            result += i - (stack_pos[current].front() + fwget(stack_pos[current].front()));
            
            fwadd(stack_pos[current].front(), 1);
            fwadd(i, -1);
            
            stack_pos[current].pop_front();
        }
        else if (left) stack_neg[current].push_back(i);
        
        if (!left && stack_neg[current].size())
        {
            printf("positive %i in index %i got a pair in %i (%i)\n", current, i, stack_neg[current].front(), stack_neg[current].front() + fwget(stack_neg[current].front()));
            result += i - (stack_neg[current].front() + fwget(stack_neg[current].front())) - 1;
            
            fwadd(stack_neg[current].front() + 1, 1);
            fwadd(i, -1);
            
            stack_neg[current].pop_front();
        }
        else if (!left) stack_pos[current].push_back(i);
    }
    
    // std::cout << result << std::endl;
	return result;
}

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