oj.uz

Submission #535301

# Submission time Handle Problem Language Result Execution time Memory
535301 2022-03-10T01:22:32 Z Deepesson Unscrambling a Messy Bug (IOI16_messy) C++17
100 / 100
 2 ms 480 KB 
#include <bits/stdc++.h>

#include "messy.h"
void divide(int la,int ra,std::string tot){
    if(la==ra){
        return;
    }
    int m = (la+ra)/2;
    ///Adiciona N/2 elementos por nivel
    for(int i=la;i<=m;++i){
        std::string x = tot;
        x[i]='1';
        add_element(x);
    }
    {
        std::string copia = tot;
        for(int i=m+1;i<=ra;++i){
            copia[i]='1';
        }
        divide(la,m,copia);
    }
    {
        std::string copia = tot;
        for(int i=la;i<=m;++i){
            copia[i]='1';
        }
        divide(m+1,ra,copia);
    }
}
int indices[300];
void gerar(int la,int ra,std::vector<int> valido,std::string lixo){
    if(la==ra){
      ///  std::cout<<valido.size()<<"\n";
        assert(valido.size()==1);
        indices[valido[0]]=la;
        return;
    }
  ///  std::cout<<valido.size()<<" "<<(ra-la+1)<<" "<<la<<" "<<ra<<"\n";
    std::vector<int> a,b;
    for(auto&x:valido){
        std::string copia = lixo;
        copia[x]='1';
        bool res = check_element(copia);
        if(res){
            a.push_back(x);
        }else b.push_back(x);
    }
 ///   std::cout<<valido.size()<<" "<<(ra-la+1)<<" "<<a.size()<<" "<<b.size()<<"\n";
    int m = (la+ra)/2;
    {
        std::string novastr=lixo;
        for(auto&x:b)novastr[x]='1';
        gerar(la,m,a,novastr);
    }
    {
        std::string novastr=lixo;
        for(auto&x:a)novastr[x]='1';
        gerar(m+1,ra,b,novastr);
    }
}
std::vector<int> restore_permutation(int n, int w, int r) {
    std::string g;
    for(int i=0;i!=n;++i)g+='0';
    std::vector<int> a;
    for(int i=0;i!=n;++i)a.push_back(i);
  ///  std::cout<<a.size()<<"!!\n";
    divide(0,n-1,g);
  ///  std::cout<<"ok\n";
    compile_set();
    gerar(0,n-1,a,g);
    std::vector<int> ans;
    for(int i=0;i!=n;++i)ans.push_back(indices[i]);

    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB n = 8
2 Correct 0 ms 212 KB n = 8
3 Correct 0 ms 304 KB n = 8
4 Correct 0 ms 212 KB n = 8
5 Correct 0 ms 212 KB n = 8
6 Correct 0 ms 212 KB n = 8
7 Correct 1 ms 212 KB n = 8
8 Correct 0 ms 304 KB n = 8
9 Correct 0 ms 212 KB n = 8
10 Correct 0 ms 340 KB n = 8
11 Correct 0 ms 212 KB n = 8
12 Correct 0 ms 212 KB n = 8
13 Correct 0 ms 212 KB n = 8
14 Correct 1 ms 212 KB n = 8
15 Correct 0 ms 212 KB n = 8

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 1 ms 212 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 0 ms 212 KB n = 32
6 Correct 0 ms 212 KB n = 32
7 Correct 1 ms 312 KB n = 32
8 Correct 1 ms 212 KB n = 32
9 Correct 1 ms 212 KB n = 32
10 Correct 1 ms 308 KB n = 32
11 Correct 1 ms 312 KB n = 32
12 Correct 1 ms 212 KB n = 32
13 Correct 0 ms 212 KB n = 32
14 Correct 0 ms 308 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 32
2 Correct 0 ms 308 KB n = 32
3 Correct 1 ms 212 KB n = 32
4 Correct 1 ms 212 KB n = 32
5 Correct 1 ms 212 KB n = 32
6 Correct 1 ms 212 KB n = 32
7 Correct 1 ms 212 KB n = 32
8 Correct 1 ms 340 KB n = 32
9 Correct 1 ms 212 KB n = 32
10 Correct 1 ms 304 KB n = 32
11 Correct 1 ms 308 KB n = 32
12 Correct 1 ms 316 KB n = 32
13 Correct 1 ms 304 KB n = 32
14 Correct 1 ms 212 KB n = 32
15 Correct 1 ms 212 KB n = 32

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB n = 128
2 Correct 1 ms 468 KB n = 128
3 Correct 1 ms 468 KB n = 128
4 Correct 1 ms 468 KB n = 128
5 Correct 2 ms 468 KB n = 128
6 Correct 1 ms 432 KB n = 128
7 Correct 1 ms 468 KB n = 128
8 Correct 1 ms 468 KB n = 128
9 Correct 1 ms 468 KB n = 128
10 Correct 1 ms 468 KB n = 128
11 Correct 1 ms 468 KB n = 128
12 Correct 1 ms 468 KB n = 128
13 Correct 2 ms 468 KB n = 128
14 Correct 1 ms 468 KB n = 128
15 Correct 2 ms 468 KB n = 128

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 480 KB n = 128
2 Correct 1 ms 468 KB n = 128
3 Correct 1 ms 468 KB n = 128
4 Correct 1 ms 432 KB n = 128
5 Correct 1 ms 468 KB n = 128
6 Correct 1 ms 468 KB n = 128
7 Correct 1 ms 464 KB n = 128
8 Correct 2 ms 436 KB n = 128
9 Correct 1 ms 468 KB n = 128
10 Correct 2 ms 436 KB n = 128
11 Correct 1 ms 468 KB n = 128
12 Correct 1 ms 468 KB n = 128
13 Correct 1 ms 468 KB n = 128
14 Correct 1 ms 468 KB n = 128
15 Correct 2 ms 436 KB n = 128