oj.uz

답안 #239832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239832 2020-06-17T11:13:45 Z Ruxandra985 Unscrambling a Messy Bug (IOI16_messy) C++14
100 / 100
 7 ms 512 KB 
#include <bits/stdc++.h>
#include "messy.h"

using namespace std;


string x;
vector <int> sol;

void solve (int st , int dr , vector <int> now){ /// returneaza ordinea din intervalul st ... dr
    int mid = (st + dr)/2 , i;
    vector <int> l , r;

    if (st == dr){

        //printf ("%d %d\n", now[0] , st);
        sol[now[0]] = st;

        return;
    }
    for (i = 0 ; i < (dr - st + 1) ; i++){

        x[now[i]] = '1';

        if (check_element(x))
            l.push_back(now[i]);
        else r.push_back(now[i]);

        x[now[i]] = '0';

    }

    /// elementele din l sunt in setul din stanga, cele din r in setul din dreapta


    for (i = 0 ; i < l.size() ; i++)
        x[l[i]] = '1';

    solve(mid + 1 , dr , r);

    for (i = 0 ; i < l.size() ; i++)
        x[l[i]] = '0';

    /// --------------------------------

    for (i = 0 ; i < r.size() ; i++)
        x[r[i]] = '1';

    solve(st , mid , l);

    for (i = 0 ; i < r.size() ; i++)
        x[r[i]] = '0';


}

void inser (int st , int dr){
    int mid = (st + dr) / 2 , i;

    if (st == dr)
        return;

    for (i = 0 ; i < (dr - st + 1) / 2 ; i++){

        x[i + st] = '1';

        add_element(x);
        x[i + st] = '0';

    }


    for (i = st ; i <= mid ; i++)
        x[i] = '1';

    inser(mid + 1 , dr);

    for (i = st ; i <= mid ; i++)
        x[i] = '0';

    /// --------------------------------

    for (i = mid + 1 ; i <= dr ; i++)
        x[i] = '1';

    inser(st , mid);

    for (i = mid + 1 ; i <= dr ; i++)
        x[i] = '0';

}

vector<int> restore_permutation(int n, int w, int r) {
    int i;
    /// setul de inserat e constant
    vector <int> now;

    x.resize(n , '0');

    for (i = 0 ; i < n / 2 ; i++){
        x[i] = '1';
        add_element(x);
        x[i] = '0';
    }

    inser (0 , n - 1);

    compile_set();

    for (i = 0 ; i < n ; i++)
        now.push_back(i);

    sol.resize(n , 0);

    solve (0 , n - 1 , now);

    return sol;
}

Compilation message

messy.cpp: In function 'void solve(int, int, std::vector<int>)':
messy.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < l.size() ; i++)
                  ~~^~~~~~~~~~
messy.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < l.size() ; i++)
                  ~~^~~~~~~~~~
messy.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < r.size() ; i++)
                  ~~^~~~~~~~~~
messy.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0 ; i < r.size() ; i++)
                  ~~^~~~~~~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 256 KB n = 8
2 Correct 4 ms 256 KB n = 8
3 Correct 5 ms 384 KB n = 8
4 Correct 5 ms 384 KB n = 8
5 Correct 4 ms 256 KB n = 8
6 Correct 4 ms 256 KB n = 8
7 Correct 5 ms 256 KB n = 8
8 Correct 5 ms 384 KB n = 8
9 Correct 5 ms 384 KB n = 8
10 Correct 5 ms 384 KB n = 8
11 Correct 4 ms 384 KB n = 8
12 Correct 4 ms 256 KB n = 8
13 Correct 5 ms 384 KB n = 8
14 Correct 5 ms 256 KB n = 8
15 Correct 5 ms 256 KB n = 8

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 32
2 Correct 5 ms 384 KB n = 32
3 Correct 5 ms 384 KB n = 32
4 Correct 5 ms 384 KB n = 32
5 Correct 5 ms 384 KB n = 32
6 Correct 5 ms 384 KB n = 32
7 Correct 5 ms 384 KB n = 32
8 Correct 5 ms 384 KB n = 32
9 Correct 5 ms 384 KB n = 32
10 Correct 5 ms 384 KB n = 32
11 Correct 5 ms 384 KB n = 32
12 Correct 5 ms 384 KB n = 32
13 Correct 5 ms 384 KB n = 32
14 Correct 5 ms 384 KB n = 32
15 Correct 5 ms 384 KB n = 32

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB n = 32
2 Correct 5 ms 256 KB n = 32
3 Correct 5 ms 384 KB n = 32
4 Correct 5 ms 384 KB n = 32
5 Correct 5 ms 384 KB n = 32
6 Correct 5 ms 384 KB n = 32
7 Correct 5 ms 384 KB n = 32
8 Correct 5 ms 384 KB n = 32
9 Correct 5 ms 384 KB n = 32
10 Correct 5 ms 384 KB n = 32
11 Correct 5 ms 384 KB n = 32
12 Correct 5 ms 384 KB n = 32
13 Correct 5 ms 384 KB n = 32
14 Correct 5 ms 384 KB n = 32
15 Correct 5 ms 384 KB n = 32

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB n = 128
2 Correct 6 ms 512 KB n = 128
3 Correct 6 ms 512 KB n = 128
4 Correct 6 ms 512 KB n = 128
5 Correct 6 ms 512 KB n = 128
6 Correct 6 ms 512 KB n = 128
7 Correct 6 ms 512 KB n = 128
8 Correct 6 ms 512 KB n = 128
9 Correct 6 ms 512 KB n = 128
10 Correct 6 ms 512 KB n = 128
11 Correct 7 ms 512 KB n = 128
12 Correct 6 ms 512 KB n = 128
13 Correct 6 ms 512 KB n = 128
14 Correct 6 ms 512 KB n = 128
15 Correct 6 ms 512 KB n = 128

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB n = 128
2 Correct 6 ms 512 KB n = 128
3 Correct 6 ms 512 KB n = 128
4 Correct 6 ms 512 KB n = 128
5 Correct 6 ms 512 KB n = 128
6 Correct 6 ms 512 KB n = 128
7 Correct 6 ms 512 KB n = 128
8 Correct 6 ms 512 KB n = 128
9 Correct 6 ms 512 KB n = 128
10 Correct 6 ms 512 KB n = 128
11 Correct 6 ms 512 KB n = 128
12 Correct 6 ms 512 KB n = 128
13 Correct 6 ms 512 KB n = 128
14 Correct 6 ms 512 KB n = 128
15 Correct 6 ms 512 KB n = 128