Submission #554597

#	Time	Username	Problem	Language	Result	Execution time	Memory
554597		urosk	Data Transfer (IOI19_transfer)	C++14	80 / 100	182 ms	2496 KiB

transfer

#include "transfer.h"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;

vector<int> get_attachment(vector<int> a) {
    int n = sz(a);
    int x = 0;
    vector<int> ans;
    for(int i = 0;i<n;i++){
        if(a[i]==0) x^=1;
    }
    ans.pb(x);
    ans.pb(x);
    x = 0;
    ll nn = n+1;
    ll d =0;
    while(nn>0){
        nn/=2;
        d++;
    }
    d--;
    for(ll i = 0;i<n;i++){
        if(a[i]==0) x^=i;
    }
    //acerr<<d<<" "<<x<<endl;
    while(x>0){
        d--;
        ans.pb(x&1);
        x/=2;
    }
    while(d--) ans.pb(0);
    return ans;
}
//n 4 n/2
vector<int> retrieve(vector<int> a) {
    int m = sz(a);
    int n = 1;
    while(1){
        ll g = 0;
        ll f = n;
        while(f>0){
            f/=2;
            g++;
        }
        if(n+g+1<m){
            n++;
            continue;
        }
        break;
    }
    n--;
    //cerr<<n<<" "<<m<<endl;
    vector<int> ans;
    ll x = 0;
    for(ll i = n+2;i<sz(a);i++){
        x+=a[i]*(1<<(i-n-2));
    }
    ll y = 0;
    ll z = 0;
    for(ll i = 0;i<n;i++){
        ans.pb(a[i]);
        if(a[i]==0){
            y^=i;
            z^=1;
        }
    }
    if(a[n]!=a[n+1])return ans;
    if(z==a[n]) return ans;
    x^=y;
    ans[x]^=1;
    return ans;
}
/*
1
4 010101011
*/

• Subtask 1: 48 / 60
• Subtask 2: 32 / 40