oj.uz

Submission #1040917

# Submission time Handle Problem Language Result Execution time Memory
1040917 2024-08-01T12:02:56 Z eitanelb The Collection Game (BOI21_swaps) C++14
100 / 100
 5 ms 1092 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 2 ms 552 KB Correct
5 Correct 3 ms 576 KB Correct
6 Correct 2 ms 344 KB Correct
7 Correct 3 ms 344 KB Correct
8 Correct 2 ms 584 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 3 ms 344 KB Correct
5 Correct 2 ms 344 KB Correct
6 Correct 3 ms 344 KB Correct
7 Correct 2 ms 552 KB Correct
8 Correct 3 ms 344 KB Correct
9 Correct 3 ms 552 KB Correct
10 Correct 3 ms 556 KB Correct
11 Correct 2 ms 344 KB Correct
12 Correct 4 ms 344 KB Correct
13 Correct 5 ms 1024 KB Correct

Subtask #3-1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 344 KB Correct

Subtask #3-2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 1 ms 344 KB Correct
3 Correct 0 ms 344 KB Correct
4 Correct 0 ms 344 KB Correct

Subtask #4-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 344 KB Correct
3 Correct 2 ms 344 KB Correct
4 Correct 2 ms 344 KB Correct

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 344 KB Correct
3 Correct 2 ms 344 KB Correct
4 Correct 2 ms 344 KB Correct
5 Correct 0 ms 344 KB Correct
6 Correct 0 ms 344 KB Correct
7 Correct 1 ms 344 KB Correct
8 Correct 3 ms 852 KB Correct
9 Correct 4 ms 344 KB Correct
10 Correct 2 ms 344 KB Correct
11 Correct 3 ms 556 KB Correct
12 Correct 2 ms 344 KB Correct
13 Correct 0 ms 344 KB Correct
14 Correct 1 ms 344 KB Correct
15 Correct 1 ms 344 KB Correct
16 Correct 2 ms 344 KB Correct

Subtask #5-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 3 ms 344 KB Correct
5 Correct 2 ms 428 KB Correct

Subtask #5-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 0 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 3 ms 344 KB Correct
5 Correct 2 ms 428 KB Correct
6 Correct 0 ms 344 KB Correct
7 Correct 1 ms 344 KB Correct
8 Correct 1 ms 344 KB Correct
9 Correct 3 ms 764 KB Correct
10 Correct 2 ms 344 KB Correct
11 Correct 2 ms 344 KB Correct
12 Correct 2 ms 344 KB Correct
13 Correct 3 ms 344 KB Correct
14 Correct 2 ms 344 KB Correct
15 Correct 3 ms 344 KB Correct
16 Correct 2 ms 560 KB Correct
17 Correct 2 ms 344 KB Correct
18 Correct 2 ms 344 KB Correct
19 Correct 0 ms 344 KB Correct
20 Correct 0 ms 344 KB Correct
21 Correct 1 ms 344 KB Correct
22 Correct 2 ms 556 KB Correct
23 Correct 2 ms 344 KB Correct

Subtask #6-1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 2 ms 552 KB Correct
5 Correct 2 ms 344 KB Correct
6 Correct 3 ms 556 KB Correct

Subtask #6-2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 2 ms 552 KB Correct
5 Correct 2 ms 344 KB Correct
6 Correct 3 ms 556 KB Correct
7 Correct 1 ms 344 KB Correct
8 Correct 1 ms 344 KB Correct
9 Correct 1 ms 344 KB Correct
10 Correct 3 ms 1092 KB Correct
11 Correct 3 ms 556 KB Correct
12 Correct 2 ms 552 KB Correct
13 Correct 2 ms 344 KB Correct
14 Correct 2 ms 556 KB Correct
15 Correct 2 ms 344 KB Correct
16 Correct 2 ms 560 KB Correct
17 Correct 2 ms 344 KB Correct
18 Correct 2 ms 344 KB Correct
19 Correct 3 ms 548 KB Correct
20 Correct 0 ms 344 KB Correct
21 Correct 0 ms 344 KB Correct
22 Correct 1 ms 344 KB Correct
23 Correct 4 ms 552 KB Correct
24 Correct 2 ms 344 KB Correct
25 Correct 4 ms 556 KB Correct

Subtask #7-1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 2 ms 344 KB Correct
5 Correct 2 ms 344 KB Correct
6 Correct 2 ms 532 KB Correct
7 Correct 3 ms 532 KB Correct

Subtask #7-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 344 KB Correct
3 Correct 1 ms 344 KB Correct
4 Correct 2 ms 344 KB Correct
5 Correct 2 ms 344 KB Correct
6 Correct 2 ms 532 KB Correct
7 Correct 3 ms 532 KB Correct
8 Correct 0 ms 344 KB Correct
9 Correct 0 ms 344 KB Correct
10 Correct 0 ms 344 KB Correct
11 Correct 1 ms 344 KB Correct
12 Correct 2 ms 344 KB Correct
13 Correct 4 ms 344 KB Correct
14 Correct 3 ms 344 KB Correct
15 Correct 3 ms 344 KB Correct
16 Correct 2 ms 344 KB Correct
17 Correct 3 ms 552 KB Correct
18 Correct 2 ms 564 KB Correct
19 Correct 2 ms 556 KB Correct
20 Correct 2 ms 344 KB Correct
21 Correct 2 ms 344 KB Correct
22 Correct 0 ms 344 KB Correct
23 Correct 1 ms 344 KB Correct
24 Correct 1 ms 344 KB Correct
25 Correct 2 ms 556 KB Correct
26 Correct 2 ms 556 KB Correct
27 Correct 3 ms 548 KB Correct
28 Correct 2 ms 408 KB Correct