oj.uz

Submission #1040273

# Submission time Handle Problem Language Result Execution time Memory
1040273 2024-07-31T21:51:47 Z eitanelb The Collection Game (BOI21_swaps) C++14
35 / 100
 33 ms 712 KB 
//
// --- 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 436 KB Correct
3 Correct 7 ms 596 KB Correct
4 Correct 27 ms 440 KB Correct
5 Correct 26 ms 680 KB Correct
6 Correct 24 ms 440 KB Correct
7 Correct 22 ms 444 KB Correct
8 Correct 25 ms 448 KB Correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 6 ms 344 KB Correct
4 Correct 25 ms 600 KB Correct
5 Correct 22 ms 444 KB Correct
6 Correct 21 ms 448 KB Correct
7 Correct 22 ms 440 KB Correct
8 Correct 23 ms 448 KB Correct
9 Correct 22 ms 600 KB Correct
10 Correct 21 ms 468 KB Correct
11 Correct 24 ms 712 KB Correct
12 Correct 22 ms 444 KB Correct
13 Correct 22 ms 472 KB Correct

Subtask #3-1
3.0 / 3.0

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

Subtask #3-2
2.0 / 2.0

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

Subtask #4-1
9.0 / 9.0

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

Subtask #4-2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 6 ms 344 KB Correct
4 Correct 33 ms 440 KB Correct
5 Correct 0 ms 344 KB Correct
6 Correct 1 ms 344 KB Correct
7 Correct 7 ms 344 KB Correct
8 Correct 23 ms 556 KB Correct
9 Correct 23 ms 452 KB Correct
10 Correct 24 ms 456 KB Correct
11 Correct 24 ms 600 KB Correct
12 Correct 21 ms 472 KB Correct
13 Correct 0 ms 344 KB Correct
14 Correct 2 ms 436 KB Correct
15 Correct 10 ms 344 KB Correct
16 Correct 23 ms 452 KB Correct

Subtask #5-1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 6 ms 600 KB Correct
4 Correct 21 ms 444 KB Correct
5 Runtime error 11 ms 600 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #5-2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 2 ms 344 KB Correct
3 Correct 6 ms 600 KB Correct
4 Correct 21 ms 444 KB Correct
5 Runtime error 11 ms 600 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 436 KB Correct
3 Correct 8 ms 444 KB Correct
4 Correct 27 ms 444 KB Correct
5 Runtime error 13 ms 448 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #6-2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Correct
2 Correct 1 ms 436 KB Correct
3 Correct 8 ms 444 KB Correct
4 Correct 27 ms 444 KB Correct
5 Runtime error 13 ms 448 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #7-1
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 7 ms 344 KB Correct
4 Correct 21 ms 600 KB Correct
5 Runtime error 17 ms 600 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -

Subtask #7-2
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 7 ms 344 KB Correct
4 Correct 21 ms 600 KB Correct
5 Runtime error 17 ms 600 KB Execution killed with signal 13
6 Halted 0 ms 0 KB -