Submission #1040917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040917		eitanelb	The Collection Game (BOI21_swaps)	C++14	100 / 100	5 ms	1092 KiB

swaps

#include "swaps.h"
#include<bits/stdc++.h>
using namespace std;
#define pi pair<int,int>
#define x first
#define y second

vector<vector<pi>> vec(50);
void rhc(int s, int e, int n, int i){
    for(int j=0;j<n/2;j++){
        vec[i].push_back({s+j,e-j});
    }
}
void hc(int s, int e, int n, int i){
    for(int j=0;j<n/2;j++){
        vec[i].push_back({s+j,s+n/2+j});
    }
}
int bs(int s, int e, int n, int i){
    if(n==1) return i;
    int m = s + n/2 - 1;
    hc(s,e,n,i);
    int u = bs(s,m,n/2,i+1);
    bs(m+1,e,n/2,i+1);
    return u;
}
int merger(int s, int e, int n, int i){
    if(n==1) return i;
    int m = s + n/2 - 1;
    rhc(s,e,n,i);
    int u = bs(s,m,n/2,i+1);
    bs(m+1,e,n/2,i+1);
    return u;
}
int sorter(int s, int e, int n, int i){
    if(n==1) return i;
    int m = s + n/2 - 1;
    int u = sorter(s,m,n/2,i);
    sorter(m+1,e,n/2,i);
    u = merger(s,e,n,u);
    return u;
}

void solve(int N, int V) {
    int n=N;
    int p=1; while(p<n)p<<=1;
    int z = sorter(1,p,p,0);
    vector<int> v(N); for(int i=0;i<N;i++) v[i]=i+1;
    
    for(int i=0;i<z;i++){
        vector<int> o(vec[i].size());
        int c=0;
        for(int j=0;j<vec[i].size();j++) if(vec[i][j].y<=n){ o[j]=c++; schedule(v[vec[i][j].x-1],v[vec[i][j].y-1]); }
        vector<int> w = visit();
        for(int j=0;j<vec[i].size();j++) if(vec[i][j].y<=n &&  w[o[j]]==0) swap(v[vec[i][j].x-1],v[vec[i][j].y-1]);
    }
    answer(v);
}

Compilation message (stderr)

swaps.cpp: In function 'void solve(int, int)':
swaps.cpp:53:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(int j=0;j<vec[i].size();j++) if(vec[i][j].y<=n){ o[j]=c++; schedule(v[vec[i][j].x-1],v[vec[i][j].y-1]); }
      |                     ~^~~~~~~~~~~~~~
swaps.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j=0;j<vec[i].size();j++) if(vec[i][j].y<=n &&  w[o[j]]==0) swap(v[vec[i][j].x-1],v[vec[i][j].y-1]);
      |                     ~^~~~~~~~~~~~~~

• 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: 9 / 9
• Subtask 5-2: 6 / 6
• Subtask 6-1: 21 / 21
• Subtask 6-2: 14 / 14
• Subtask 7-1: 9 / 9
• Subtask 7-2: 6 / 6