Submission #1040273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040273		eitanelb	The Collection Game (BOI21_swaps)	C++14	35 / 100	33 ms	712 KiB

swaps

//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
//     swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include<bits/stdc++.h>
using namespace std;

vector<int> merge_sort(vector<int> v, int n){
    if(n==1) return v;
    vector<int> v1(n/2), v2((n+1)/2);
    for(int i=0;i<n/2;i++) v1[i]=v[i];
    for(int i=n/2;i<n;i++) v2[i-n/2]=v[i];
    v1=merge_sort(v1,n/2);
    v2=merge_sort(v2,(n+1)/2);
    int p1=0,p2=0,p=0;
    while(p1<n/2 || p2<(n+1)/2){
        if(p1 == n/2){ v[p++]=v2[p2++]; continue; }
        if(p2 == (n+1)/2){ v[p++]=v1[p1++]; continue; }
        
        schedule(v1[p1], v2[p2]);
        vector<int> a=visit();
        
        if(a[0] == 1) v[p++] = v1[p1++];
        else v[p++]=v2[p2++];
    }
    return v;
}

void solve(int N, int V) {
    int n=N;
    vector<int> v(N); for(int i=0;i<N;i++) v[i]=i+1;
    //v=merge_sort(v,N);
    
    for(int i=1;i<n;i++){
        int j=2;
        if(i%2) j=1;
        for(int u=j;u<=i;u+=2) schedule(v[u-1],v[u]);
        vector<int> w = visit();
        for(int u=j;u<=i;u+=2) if(w[(u-1)/2]==0) swap(v[u],v[u-1]);
    }
    for(int i=n-2;i>0;i--){
        int j=2;
        if(i%2) j=1;
        for(int u=j;u<=i;u+=2) schedule(v[u-1],v[u]);
        vector<int> w = visit();
        for(int u=j;u<=i;u+=2) if(w[(u-1)/2]==0) swap(v[u],v[u-1]);
    }
    answer(v);
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3-1: 3 / 3
• Subtask 3-2: 2 / 2
• Subtask 4-1: 9 / 9
• Subtask 4-2: 6 / 6
• Subtask 5-1: 0 / 9
• Subtask 5-2: 0 / 6
• Subtask 6-1: 0 / 21
• Subtask 6-2: 0 / 14
• Subtask 7-1: 0 / 9
• Subtask 7-2: 0 / 6