제출 #652033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
652033		TimDee	Flight to the Ford (BOI22_communication)	C++17	0 / 100	8000 ms	82444 KiB

communication

#include"communication.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)

vector<int> V;
void brut(int x, int n, int v=0, int i=0, int l=0) {
    if (i>=n) {V.push_back(v); return;}
    int b=(x>>i)&1;
    brut(x,n,v+(b<<i),i+1,0);
    if (l==0) brut(x,n,v+((!b)<<i),i+1,1);
}

vector<int> get_possible(int n) {
    int x=0, q=0;
    forn(i,29) {
        q=receive();
        x+=q<<i;
    }
    brut(x,29,0,0,0);
    vector<int> b;
    set<int> s;
    for (auto x:V) {
        if (x>=n) continue;
        for (int i=0; i+x<n; i+=1<<29) {
            s.insert(x);
        }
    }
    for (auto x:s) b.push_back(x);
    V.clear();
    return b;
}

vector<int> dequery(vector<int>&a,int bit) {
    int x=0, q;
    forn(i,bit) x+=receive()<<i;
    brut(x,bit);

    vector<int> b;
    set<int> s;
    for (auto x:V) {
        if (x>=a.size()) continue;
        for (int i=0; i+x<a.size(); i+=(1<<bit)) {
            s.insert(a[i+x]);
        }
    }
    for (auto x:s) b.push_back(x);
    V.clear();
    return b;

}

pair<int,int> decode(int n) {
    
    vector<int> a=get_possible(n); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    a=dequery(a,21);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};
    a=dequery(a,15);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};
    a=dequery(a,11);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};
    a=dequery(a,8);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};
    a=dequery(a,6);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};
    a=dequery(a,4);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};
    a=dequery(a,3);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};

    a=dequery(a,4);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};
    a=dequery(a,3);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};
    a=dequery(a,2);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};
    a=dequery(a,2);
    if (a.size()==3) {
        int q,x=0;
        q=receive();
        x+=q<<0;
        q=receive();
        x+=q<<1;
        q=receive();
        x+=q<<2;
        q=receive();
        x+=q<<3;

        vector<int> ans;
        vector<int> A={0,1,5,10,9,8,2,4};
        vector<int> B={1,8,9,11,13,3,12,0};
        vector<int> C={6,15,2,4,12,3,7,14};
        for (auto v:A) if (v==x) ans.push_back(a[0]);
        for (auto v:B) if (v==x) ans.push_back(a[1]);
        for (auto v:C) if (v==x) ans.push_back(a[2]);

        if (ans.size()==1) return {ans[0]+1,ans[0]+1};
        return {ans[0]+1,ans[1]+1};
    }
    if (a.size()==2) return {a[0]+1,a[1]+1};
    if (a.size()==1) return {a[0]+1,a[0]+1};

    if (a.size()==1) return{a[0]+1,a[0]+1};
    if (a.size()==2) return{a[0]+1,a[1]+1};
    assert(a.size()==3);

    int q,x=0;
    q=receive();
    x+=q<<0;
    q=receive();
    x+=q<<1;
    q=receive();
    x+=q<<2;
    q=receive();
    x+=q<<3;

    vector<int> ans;
    vector<int> A={0,1,5,10,9,8,2,4};
    vector<int> B={1,8,9,11,13,3,12,0};
    vector<int> C={6,15,2,4,12,3,7,14};
    for (auto v:A) if (v==x) ans.push_back(a[0]);
    for (auto v:B) if (v==x) ans.push_back(a[1]);
    for (auto v:C) if (v==x) ans.push_back(a[2]);

    if (ans.size()==1) return {ans[0]+1,ans[0]+1};
    return {ans[0]+1,ans[1]+1};

}

int Send(int x, int bit) {
    int ret=0;
    forn(i,bit) ret+=send((x>>i)&1)<<i;
    return ret;
}

vector<int> get_possible(int n, int x) {
    x=Send(x,29);
    brut(x,29);
    vector<int> b;
    set<int> s;
    for (auto x:V) {
        if (x>=n) continue;
        for (int i=0; i+x<n; i+=1<<29) {
            s.insert(x);
        }
    }
    for (auto x:s) b.push_back(x);
    V.clear();
    return b;
}

vector<int> query(vector<int>&a,int x,int bit) {
    int l=0,r=a.size()-1;
    while (l<r) {
        int mid=(l+r+1)>>1;
        if (a[mid]>x) r=mid-1;
        else l=mid;
    }
    r=Send(r,bit);
    brut(r,bit);
    vector<int> b;
    set<int> s;
    for (auto x:V) {
        if (x>=a.size()) continue;
        for (int i=0; i+x<a.size(); i+=(1<<bit)) {
            s.insert(a[i+x]);
        }
    }
    for (auto x:s) b.push_back(x);
    V.clear();
    return b;

}

void encode(int n, int x) {

    --x;
    vector<int> a=get_possible(n,x); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    a=query(a,x,21); 
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;
    a=query(a,x,15);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;
    a=query(a,x,11);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;
    a=query(a,x,8);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;
    a=query(a,x,6);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;
    a=query(a,x,4);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;
    a=query(a,x,3);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;

    a=query(a,x,4);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;
    a=query(a,x,3);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;
    a=query(a,x,2);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;
    a=query(a,x,2);
    if (a.size()==3) {
        int v=0,b=0;
        if (x==a[0]) {
            b=send(0);
            b=send(0);
            b=send(0);
            b=send(0);
        } else if (x==a[1]) {
            b=send(0);
            b=send(1);
            b=send(1);
            b=send(0);
        } else {
            b=send(1);
            b=send(0);
            b=send(0);
            b=send(1);
        }
        return;
    }
    if (a.size()<3) return;

    if (a.size()<3) return;

    assert(a.size()==3);
    int v=0,b=0;
    if (x==a[0]) {
        b=send(0);
        b=send(0);
        b=send(0);
        b=send(0);
    } else if (x==a[1]) {
        b=send(0);
        b=send(1);
        b=send(1);
        b=send(0);
    } else {
        b=send(1);
        b=send(0);
        b=send(0);
        b=send(1);
    }
    
}

컴파일 시 표준 에러 (stderr) 메시지

communication.cpp: In function 'std::vector<int> dequery(std::vector<int>&, int)':
communication.cpp:42:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         if (x>=a.size()) continue;
      |             ~^~~~~~~~~~
communication.cpp:43:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int i=0; i+x<a.size(); i+=(1<<bit)) {
      |                       ~~~^~~~~~~~~
communication.cpp:35:14: warning: unused variable 'q' [-Wunused-variable]
   35 |     int x=0, q;
      |              ^
communication.cpp: In function 'std::vector<int> query(std::vector<int>&, int, int)':
communication.cpp:394:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  394 |         if (x>=a.size()) continue;
      |             ~^~~~~~~~~~
communication.cpp:395:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  395 |         for (int i=0; i+x<a.size(); i+=(1<<bit)) {
      |                       ~~~^~~~~~~~~
communication.cpp: In function 'void encode(int, int)':
communication.cpp:411:13: warning: unused variable 'v' [-Wunused-variable]
  411 |         int v=0,b=0;
      |             ^
communication.cpp:411:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  411 |         int v=0,b=0;
      |                 ^
communication.cpp:433:13: warning: unused variable 'v' [-Wunused-variable]
  433 |         int v=0,b=0;
      |             ^
communication.cpp:433:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  433 |         int v=0,b=0;
      |                 ^
communication.cpp:455:13: warning: unused variable 'v' [-Wunused-variable]
  455 |         int v=0,b=0;
      |             ^
communication.cpp:455:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  455 |         int v=0,b=0;
      |                 ^
communication.cpp:477:13: warning: unused variable 'v' [-Wunused-variable]
  477 |         int v=0,b=0;
      |             ^
communication.cpp:477:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  477 |         int v=0,b=0;
      |                 ^
communication.cpp:499:13: warning: unused variable 'v' [-Wunused-variable]
  499 |         int v=0,b=0;
      |             ^
communication.cpp:499:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  499 |         int v=0,b=0;
      |                 ^
communication.cpp:521:13: warning: unused variable 'v' [-Wunused-variable]
  521 |         int v=0,b=0;
      |             ^
communication.cpp:521:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  521 |         int v=0,b=0;
      |                 ^
communication.cpp:543:13: warning: unused variable 'v' [-Wunused-variable]
  543 |         int v=0,b=0;
      |             ^
communication.cpp:543:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  543 |         int v=0,b=0;
      |                 ^
communication.cpp:566:13: warning: unused variable 'v' [-Wunused-variable]
  566 |         int v=0,b=0;
      |             ^
communication.cpp:566:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  566 |         int v=0,b=0;
      |                 ^
communication.cpp:588:13: warning: unused variable 'v' [-Wunused-variable]
  588 |         int v=0,b=0;
      |             ^
communication.cpp:588:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  588 |         int v=0,b=0;
      |                 ^
communication.cpp:610:13: warning: unused variable 'v' [-Wunused-variable]
  610 |         int v=0,b=0;
      |             ^
communication.cpp:610:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  610 |         int v=0,b=0;
      |                 ^
communication.cpp:632:13: warning: unused variable 'v' [-Wunused-variable]
  632 |         int v=0,b=0;
      |             ^
communication.cpp:632:17: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  632 |         int v=0,b=0;
      |                 ^
communication.cpp:656:9: warning: unused variable 'v' [-Wunused-variable]
  656 |     int v=0,b=0;
      |         ^
communication.cpp:656:13: warning: variable 'b' set but not used [-Wunused-but-set-variable]
  656 |     int v=0,b=0;
      |             ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 85