Submission #655882

#	Time	Username	Problem	Language	Result	Execution time	Memory
655882		Lobo	Flight to the Ford (BOI22_communication)	C++17	100 / 100	2965 ms	2352 KiB

communication

#include"communication.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

vector<pair<int,int>> join(vector<pair<int,int>> v1, vector<pair<int,int>> v2) {
    vector<pair<int,int>> v;
    for(auto x : v1) v.pb(x);
    for(auto x : v2) v.pb(x);
    return v;
}
void encode(int N, int X) {

    int szA = N, szB = 0;
    vector<pair<int,int>> A,B;
    A.pb(mp(1,N));
    while(szA+szB >= 5) {
        int sza = szA/2,szb = szB/2;
        vector<pair<int,int>> a,b;
        while(A.size() && sza != 0) {
            int l = A.back().fr;
            int r = A.back().sc;
            A.pop_back();
            int l1 = max(l,r+1-sza);
            a.pb(mp(l1,r));
            sza-= (r-l1+1);
            if(l != l1) A.pb(mp(l,l1-1));
        }
        while(B.size() && szb != 0) {
            int l = B.back().fr;
            int r = B.back().sc;
            B.pop_back();
            int l1 = max(l,r+1-szb);
            b.pb(mp(l1,r));
            szb-= (r-l1+1);
            if(l != l1) B.pb(mp(l,l1-1));
        }

        int ans1 = 0;
        for(auto x : a) {
            if(x.fr <= X && x.sc >= X) ans1 = 1;
        }
        for(auto x : b) {
            if(x.fr <= X && x.sc >= X) ans1 = 1;
        }
        ans1 = send(ans1);

        vector<pair<int,int>> newA, newB;
        if(ans1 == 1) {
            for(auto x : a) newA.pb(x);
            for(auto x : b) newA.pb(x);
            for(auto x : A) newB = A;
        }
        else {
            for(auto x : A) newA.pb(x);
            for(auto x : B) newA.pb(x);
            for(auto x : a) newB.pb(x);
        }
        A = newA;
        B = newB;
        szA = 0;
        for(auto x : A) {
            szA+= x.sc-x.fr+1;
        }
        szB = 0;
        for(auto x : B) {
            szB+= x.sc-x.fr+1;
        }
    }


    // 0000 0110 1001 1111
    vector<int> pos[(1<<4)];
    vector<int> masks = {0,6,9,15};
    for(int i = 0; i < masks.size(); i++) {
        for(int msk = 0; msk < (1<<4); msk++) {
            int antw = 0;
            bool ok = true;
            for(int j = 0; j < 4; j++) {
                if(((1<<j)&msk) == ((1<<j)&masks[i])) {
                    antw = 0;
                }
                else {
                    if(antw == 1) ok = false;
                    antw = 1;
                }
            }

            if(ok) {
                pos[msk].pb(i);
            }
        }
    }

    vector<pair<int,int>> vec,vqr;
    for(auto x : A) vec.pb(x);
    for(auto x : B) vec.pb(x);
    int sz = szA+szB;
    while(sz >= 3) {
        vector<pair<int,int>> p[4];
        int sz1 = sz/4; sz-= sz1;
        int sz2 = sz/3; sz-= sz2;
        int sz3 = sz/2; sz-= sz3;
        int sz4 = sz;

        while(vec.size() && sz1 != 0) {
            int l = vec.back().fr;
            int r = vec.back().sc;
            vec.pop_back();
            int l1 = max(l,r+1-sz1);
            p[0].pb(mp(l1,r));
            sz1-= (r-l1+1);
            if(l1 != l) vec.pb(mp(l,l1-1));
        }
        while(vec.size() && sz2 != 0) {
            int l = vec.back().fr;
            int r = vec.back().sc;
            vec.pop_back();
            int l1 = max(l,r+1-sz2);
            p[1].pb(mp(l1,r));
            sz2-= (r-l1+1);
            if(l1 != l) vec.pb(mp(l,l1-1));
        }
        while(vec.size() && sz3 != 0) {
            int l = vec.back().fr;
            int r = vec.back().sc;
            vec.pop_back();
            int l1 = max(l,r+1-sz3);
            p[2].pb(mp(l1,r));
            sz3-= (r-l1+1);
            if(l1 != l) vec.pb(mp(l,l1-1));
        }
        p[3] = vec;
        vec.clear();
        int id0;
        for(int i = 0; i < 4; i++) {
            for(auto x : p[i]) {
                if(x.fr <= X && x.sc >= X) id0 = i;
            }
        }

        int msksend = 0;
        for(int i = 3; i >= 0; i--) {
            msksend+= (1<<i)*send(((1<<i)&masks[id0]) != 0);
        }

        int id1;
        for(auto x : pos[msksend]) {
            if(x != id0) id1 = x;
        }
        for(int i = 0; i < 4; i++) {
            if(i != id0 && i != id1) p[i].clear();
        }
        vec.clear();
        for(auto x : p[0]) vec.pb(x);
        for(auto x : p[1]) vec.pb(x);
        for(auto x : p[2]) vec.pb(x);
        for(auto x : p[3]) vec.pb(x);
        sz = 0;
        for(auto x : vec) sz+= x.sc-x.fr+1;
    }
    vector<pair<int,int>> vc1;
    for(auto x : vec) {
        for(int i = x.fr; i <= x.sc; i++) vc1.pb(mp(i,i));
    }
    vec = vc1;
}

std::pair<int, int> decode(int N) {
    
    int szA = N, szB = 0;
    vector<pair<int,int>> A,B;
    A.pb(mp(1,N));
    while(szA+szB >= 5) {
        int sza = szA/2,szb = szB/2;
        vector<pair<int,int>> a,b;
        while(A.size() && sza != 0) {
            int l = A.back().fr;
            int r = A.back().sc;
            A.pop_back();
            int l1 = max(l,r+1-sza);
            a.pb(mp(l1,r));
            sza-= (r-l1+1);
            if(l != l1) A.pb(mp(l,l1-1));
        }
        while(B.size() && szb != 0) {
            int l = B.back().fr;
            int r = B.back().sc;
            B.pop_back();
            int l1 = max(l,r+1-szb);
            b.pb(mp(l1,r));
            szb-= (r-l1+1);
            if(l != l1) B.pb(mp(l,l1-1));
        }

        int ans1 = receive();

        vector<pair<int,int>> newA, newB;
        if(ans1 == 1) {
            for(auto x : a) newA.pb(x);
            for(auto x : b) newA.pb(x);
            for(auto x : A) newB = A;
        }
        else {
            for(auto x : A) newA.pb(x);
            for(auto x : B) newA.pb(x);
            for(auto x : a) newB.pb(x);
        }
        A = newA;
        B = newB;
        szA = 0;
        for(auto x : A) {
            szA+= x.sc-x.fr+1;
        }
        szB = 0;
        for(auto x : B) {
            szB+= x.sc-x.fr+1;
        }
    }


    // 0000 0110 1001 1111
    vector<int> pos[(1<<4)];
    vector<int> masks = {0,6,9,15};
    for(int i = 0; i < masks.size(); i++) {
        for(int msk = 0; msk < (1<<4); msk++) {
            int antw = 0;
            bool ok = true;
            for(int j = 0; j < 4; j++) {
                if(((1<<j)&msk) == ((1<<j)&masks[i])) {
                    antw = 0;
                }
                else {
                    if(antw == 1) ok = false;
                    antw = 1;
                }
            }

            if(ok) {
                pos[msk].pb(i);
            }
        }
    }

    vector<pair<int,int>> vec,vqr;
    for(auto x : A) vec.pb(x);
    for(auto x : B) vec.pb(x);
    int sz = szA+szB;
    while(sz >= 3) {
        vector<pair<int,int>> p[4];
        int sz1 = sz/4; sz-= sz1;
        int sz2 = sz/3; sz-= sz2;
        int sz3 = sz/2; sz-= sz3;
        int sz4 = sz;

        while(vec.size() && sz1 != 0) {
            int l = vec.back().fr;
            int r = vec.back().sc;
            vec.pop_back();
            int l1 = max(l,r+1-sz1);
            p[0].pb(mp(l1,r));
            sz1-= (r-l1+1);
            if(l1 != l) vec.pb(mp(l,l1-1));
        }
        while(vec.size() && sz2 != 0) {
            int l = vec.back().fr;
            int r = vec.back().sc;
            vec.pop_back();
            int l1 = max(l,r+1-sz2);
            p[1].pb(mp(l1,r));
            sz2-= (r-l1+1);
            if(l1 != l) vec.pb(mp(l,l1-1));
        }
        while(vec.size() && sz3 != 0) {
            int l = vec.back().fr;
            int r = vec.back().sc;
            vec.pop_back();
            int l1 = max(l,r+1-sz3);
            p[2].pb(mp(l1,r));
            sz3-= (r-l1+1);
            if(l1 != l) vec.pb(mp(l,l1-1));
        }
        p[3] = vec;
        vec.clear();
        int msksend = 0;
        for(int i = 3; i >= 0; i--) {
            msksend+= (1<<i)*receive();
        }

        int id0,id1;
        for(auto x : pos[msksend]) {
            id0 = x;
        }
        for(auto x : pos[msksend]) {
            if(x != id0) id1 = x;
        }
        for(int i = 0; i < 4; i++) {
            if(i != id0 && i != id1) p[i].clear();
        }
        vec.clear();
        for(auto x : p[0]) vec.pb(x);
        for(auto x : p[1]) vec.pb(x);
        for(auto x : p[2]) vec.pb(x);
        for(auto x : p[3]) vec.pb(x);
        sz = 0;
        for(auto x : vec) sz+= x.sc-x.fr+1;
    }
    vector<pair<int,int>> vc1;
    for(auto x : vec) {
        for(int i = x.fr; i <= x.sc; i++) vc1.pb(mp(i,i));
    }
    vec = vc1;
    if(vec.size() == 1) return {vec[0].fr,vec[0].fr};
    else return {vec[0].fr,vec[1].fr};
}

Compilation message (stderr)

communication.cpp: In function 'void encode(int, int)':
communication.cpp:60:22: warning: variable 'x' set but not used [-Wunused-but-set-variable]
   60 |             for(auto x : A) newB = A;
      |                      ^
communication.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0; i < masks.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
communication.cpp:112:13: warning: unused variable 'sz4' [-Wunused-variable]
  112 |         int sz4 = sz;
      |             ^~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:210:22: warning: variable 'x' set but not used [-Wunused-but-set-variable]
  210 |             for(auto x : A) newB = A;
      |                      ^
communication.cpp:233:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |     for(int i = 0; i < masks.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~
communication.cpp:262:13: warning: unused variable 'sz4' [-Wunused-variable]
  262 |         int sz4 = sz;
      |             ^~~
communication.cpp: In function 'void encode(int, int)':
communication.cpp:160:30: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  160 |             if(i != id0 && i != id1) p[i].clear();
      |                            ~~^~~~~~
communication.cpp:160:18: warning: 'id0' may be used uninitialized in this function [-Wmaybe-uninitialized]
  160 |             if(i != id0 && i != id1) p[i].clear();
      |                ~~^~~~~~
communication.cpp: In function 'std::pair<int, int> decode(int)':
communication.cpp:306:30: warning: 'id1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  306 |             if(i != id0 && i != id1) p[i].clear();
      |                            ~~^~~~~~
communication.cpp:306:18: warning: 'id0' may be used uninitialized in this function [-Wmaybe-uninitialized]
  306 |             if(i != id0 && i != id1) p[i].clear();
      |                ~~^~~~~~

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