Submission #807721

#	Time	Username	Problem	Language	Result	Execution time	Memory
807721		Essa2006	Arranging Shoes (IOI19_shoes)	C++14	65 / 100	15 ms	1864 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
#include <cstdio>
#include <cassert>
using namespace std;
#define ll long long 
#define endl '\n'
#define FF firtst
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
ll count_swaps(vector<int> S){
    bool same=1;
    int n=S.size();
    for(int i=1;i<n;i++){
        if(abs(S[i])!=abs(S[i-1]))
            same=0;
    }
    if(n/2<=1000){
        int ans=0;
        for(int i=0;i<n;i++){
            if(S[i]>0){
                bool found=0;
                int ind=0;
                for(int j=0;j<i;j++){
                    if(-S[j]==S[i] && S[j+1]!=-S[j]){
                        found=1;
                        ind=j;
                        break;
                    }
                }
                if(found){
                    for(int j=i-1;j>ind;j--){
                        swap(S[j], S[j+1]);
                        ans++;
                    }
                }
            }
            else if(S[i]<0){
                bool found=0;
                int ind=0;
                for(int j=0;j<i;j++){
                    if(-S[j]==S[i] && (!j || S[j]!=-S[j-1])){
                        found=1;
                        ind=j;
                        break;
                    }
                }
                if(found){
                    for(int j=i-1;j>=ind;j--){
                        swap(S[j], S[j+1]);
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
    if(n/2>1000 && !same){
        ll ans=S.size()/2;
        return ans*(ans-1)/2;
    }
}


//int main() {
//	int n;
//	assert(1 == scanf("%d", &n));
//	vector<int> S(2 * n);
//	for (int i = 0; i < 2 * n; i++)
//		assert(1 == scanf("%d", &S[i]));
//	fclose(stdin);
//
//	long long result = count_swaps(S);
//
//	printf("%lld\n", result);
//	fclose(stdout);
//	return 0;
//}

Compilation message (stderr)

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

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