답안 #966705

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
966705 2024-04-20T08:40:08 Z berr CEOI16_icc (CEOI16_icc) C++17
0 / 100
3 ms 604 KB
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
vector<int> vis(101);


int que(vector<int> a, vector<int> b){
    int x[a.size()], y[b.size()];

    int siz_a = a.size(), siz_b=b.size();

    for(int i=0; i<siz_a; i++){
        x[i] = a[i];
    }

    for(int i=0; i<siz_b; i++){
        y[i] = b[i];
    }

    return query(siz_a, siz_b, x, y);
}

void coz(vector<int> a, vector<int> b){
     while(a.size()>1){
        vector<int> pf;
        for(int i=0; i<a.size()/2; i++){
            pf.push_back(a[i]);
        }

        if(que(pf, b)){
            a= pf;
        }
        else{
            pf.clear();
            for(int i=a.size()/2; i<a.size(); i++){
                pf.push_back(a[i]);
            }

            a=pf;
        }
    }

    while(b.size()>1){
        vector<int> pf;
        for(int i=0; i<b.size()/2; i++){
            pf.push_back(b[i]);
        }

        if(que(a, b)){
            b= pf;
        }
        else{
            pf.clear();
            for(int i=b.size()/2; i<b.size(); i++){
                pf.push_back(b[i]);
            }

            b=pf;
        }

    }
    vis[a[0]]=1; vis[b[0]]=1;

    setRoad(a[0], b[0]);
}


void run(int n){
    for(int i=0; i<n; i++) vis[i]=0;

    for(int i=0; i<n-1; i++){

        vector<int> unvisited, visited;
        
        for(int l=1; l<=n; l++){
            if(vis[l]) visited.push_back(l);
            else unvisited.push_back(l);
        }
        if(visited.size()==0 || !que(unvisited, visited)){
            vector<int> all = unvisited;
            vector<int> a, b;
                
                int size_all = all.size();
                for(int i=0; i<size_all; i++){
                    if(i<size_all/2) a.push_back(all[i]);
                    else b.push_back(all[i]);
                }

                if(que(a, b)){
                    break;
                }
                else{
                    vector<vector<int>> aa;
                    vector<vector<int>> bb;

                    while(1){
                        vector<vector<int>> new_aa;
                        vector<vector<int>> new_bb;
                        int sa=0, sb=0;
                        for(auto i: aa){    
                            vector<int> ay, by;

                            for(int l=0; l<i.size(); l++){
                                if(l<i.size()/2){
                                    ay.push_back(i[l]);
                                    sa++;
                                }
                                else if(l==i.size()/2 && i.size()%2){
                                    if(sa+1 <= sb+i.size()/2){
                                        ay.push_back(i[l]);
                                        sa++;
                                    }
                                    else{
                                        by.push_back(i[l]);
                                        sb++;
                                    }
                                }
                                else{
                                    by.push_back(i[l]);
                                    sb++;
                                }
                            }

                            if(ay.size()==0||by.size()==0) continue;
                            else{
                                new_aa.push_back(ay);
                                new_bb.push_back(by);
                            }
                        }

                        for(auto i: bb){    
                            vector<int> ay, by;

                            for(int l=0; l<i.size(); l++){
                                if(l<i.size()/2){
                                    ay.push_back(i[l]);
                                    sa++;
                                }
                                else if(l==i.size()/2 && i.size()%2){
                                    if(sa+1 <= sb+i.size()/2){
                                        ay.push_back(i[l]);
                                        sa++;
                                    }
                                    else{
                                        by.push_back(i[l]);
                                        sb++;
                                    }
                                }
                                else{
                                    by.push_back(i[l]);
                                    sb++;
                                }
                            }

                            if(ay.size()==0||by.size()==0) continue;
                            else{
                                new_aa.push_back(ay);
                                new_bb.push_back(by);
                            }
                        }

                        vector<int> ca, cb;

                        for(auto i: new_aa)
                            for(auto l: i) ca.push_back(l);
                        
                        for(auto i: new_bb)
                            for(auto l: i)
                                cb.push_back(l);

                        if(que(ca, cb)){
                            int s=-1;
                            
                            auto check=[&](int val){
                                vector<int> pf, fp;

                                for(int i=0; i<=val; i++){
                                    for(auto l: new_aa[i]){
                                        pf.push_back(l);
                                    }
                                    for(auto l: new_bb[i]){
                                        fp.push_back(l);
                                    }
                                }

                                if(que(pf, fp)) return 1;
                                return 0;
                            };

                            for(int j=6; j>=0; j--){
                                int tmp = s+(1<<j);
                                if(tmp <new_aa.size()-1){
                                    if(check(tmp)) continue;
                                    s = tmp;
                                }
                            }

                            a=new_aa[s+1]; b=new_bb[s+1];
                            break;
                        }
                        else{
                            aa=new_aa; bb=new_bb;
                        }

                    }

                   
                }


            

            coz(a, b);

        }
        else{
            coz(visited, unvisited);
        }
    }

}

Compilation message

icc.cpp: In function 'void coz(std::vector<int>, std::vector<int>)':
icc.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i=0; i<a.size()/2; i++){
      |                      ~^~~~~~~~~~~
icc.cpp:35:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             for(int i=a.size()/2; i<a.size(); i++){
      |                                   ~^~~~~~~~~
icc.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int i=0; i<b.size()/2; i++){
      |                      ~^~~~~~~~~~~
icc.cpp:54:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |             for(int i=b.size()/2; i<b.size(); i++){
      |                                   ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:103:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |                             for(int l=0; l<i.size(); l++){
      |                                          ~^~~~~~~~~
icc.cpp:104:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |                                 if(l<i.size()/2){
      |                                    ~^~~~~~~~~~~
icc.cpp:108:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                                 else if(l==i.size()/2 && i.size()%2){
      |                                         ~^~~~~~~~~~~~
icc.cpp:109:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                                     if(sa+1 <= sb+i.size()/2){
      |                                        ~~~~~^~~~~~~~~~~~~~~~
icc.cpp:134:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |                             for(int l=0; l<i.size(); l++){
      |                                          ~^~~~~~~~~
icc.cpp:135:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |                                 if(l<i.size()/2){
      |                                    ~^~~~~~~~~~~
icc.cpp:139:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |                                 else if(l==i.size()/2 && i.size()%2){
      |                                         ~^~~~~~~~~~~~
icc.cpp:140:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |                                     if(sa+1 <= sb+i.size()/2){
      |                                        ~~~~~^~~~~~~~~~~~~~~~
icc.cpp:192:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  192 |                                 if(tmp <new_aa.size()-1){
      |                                    ~~~~^~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 604 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 604 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 604 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -