Submission #652077

#	Time	Username	Problem	Language	Result	Execution time	Memory
652077		TimDee	Flight to the Ford (BOI22_communication)	C++17	0 / 100	3047 ms	5552 KiB

communication

#include"communication.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define forn(i,n) for (int i=0; i<n; ++i)

int V[3000000]; int ptr=0; int asz=0;
int a[3000000], b[3000000], bsz=0;
void brut(int x, int n, int v=0, int i=0, int l=0) {
    if (i>=n) {V[ptr++]=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) {
    ll x=0, q=0;
    forn(i,29) {
        q=receive();
        x+=q<<i;
    }
    brut(x,29);
    for (int j=0; j<ptr; ++j) {
        int x=V[j];
        if (x>=n) continue;
        for (ll i=0; i+x<n; i+=1ll<<29) {
            b[bsz++]=i+x;
        }
    }
    sort(b,b+bsz);
    ptr=0;
    asz=0;
    forn(i,bsz) a[asz++]=b[i];
    bsz=0;
}

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

    for (int j=0; j<ptr; ++j) {
        int x=V[j];
        if (x>=asz) continue;
        for (int i=0; i+x<asz; i+=(1<<bit)) {
            b[bsz++]=(a[i+x]);
        }
    }
    sort(b,b+bsz);
    ptr=0;
    asz=0;
    forn(i,bsz) a[asz++]=b[i];
    bsz=0;

}

pair<int,int> decode(int n) {
    
    if (n>3) return{1,1};
    Get_possible(n); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    dequery(21);
    dequery(15);
    dequery(11);
    dequery(8);
    dequery(6);
    dequery(4);
    dequery(3);

    dequery(4); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    dequery(3); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    dequery(2); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    dequery(2); //for (auto x:a) cout<<x<<' '; cout<<'\n';

    if (asz==1) return{a[0]+1,a[0]+1};
    if (asz==2) return{a[0]+1,a[1]+1};
    assert(asz==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[2]);
    for (auto v:C) if (v==x) ans.push_back(a[1]);

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

}

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

void get_possible(int n, ll x) {
    x=Send(x,29);
	brut(x,29);
    ptr=0; return;
    int cnt=0;
	for (int j=0; j<ptr; ++j) {
        int x=V[j];
        if (x>=n) continue;
        for (ll i=0; i+x<n; i+=1ll<<29) {
            b[bsz++]=i+x;
        }
    }
	ptr=0;
    asz=0;
    sort(b,b+bsz);
	forn(i,bsz) a[asz++]=b[i];
    bsz=0;
}

void query(int x,int bit) {
	int r=0; while (a[r]!=x) ++r;
    r=Send(r,bit);
	brut(r,bit);
	for (int j=0; j<ptr; ++j) {
        int x=V[j];
		if (x>=asz) continue;
		for (int i=0; i+x<asz; i+=(1<<bit)) {
			b[bsz++]=a[i+x];
		}
	}
    sort(b,b+bsz);
	ptr=0;
    asz=0;
	forn(i,bsz) a[asz++]=b[i];
    bsz=0;

}

void encode(int n, int x) {

	--x;
    get_possible(n,x); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    if (n>3) return;
    query(x,21);
    query(x,15);
    query(x,11);
    query(x,8);
    query(x,6);
    query(x,4);
    query(x,3);

    query(x,4); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    query(x,3); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    query(x,2); //for (auto x:a) cout<<x<<' '; cout<<'\n';
    query(x,2); //for (auto x:a) cout<<x<<' '; cout<<'\n';

    if (asz<3) return;

    //assert(asz==3);
    int v=0,b=0;;
    if (x==a[0]) {
        b=send(0);
        v+=b<<0;
        b=send(0);
        v+=b<<1;
        b=send(0);
        v+=b<<2;
        b=send(0);
        v+=b<<3;
    } else if (x==a[1]) {
        b=send(0);
        v+=b<<0;
        b=send(1);
        v+=b<<1;
        b=send(1);
        v+=b<<2;
        b=send(0);
        v+=b<<3;
    } else {
        b=send(1);
        v+=b<<0;
        b=send(0);
        v+=b<<1;
        b=send(0);
        v+=b<<2;
        b=send(1);
        v+=b<<3;
    }
    
}

Compilation message (stderr)

communication.cpp: In function 'std::vector<int> Get_possible(int)':
communication.cpp:37:1: warning: no return statement in function returning non-void [-Wreturn-type]
   37 | }
      | ^
communication.cpp: In function 'std::vector<int> dequery(int)':
communication.cpp:40:14: warning: unused variable 'q' [-Wunused-variable]
   40 |     int x=0, q;
      |              ^
communication.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
   57 | }
      | ^
communication.cpp: In function 'void get_possible(int, ll)':
communication.cpp:113:9: warning: unused variable 'cnt' [-Wunused-variable]
  113 |     int cnt=0;
      |         ^~~

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