Submission #358584

#	Time	Username	Problem	Language	Result	Execution time	Memory
358584		Ahmad_Hasan	Data Transfer (IOI19_transfer)	C++17	100 / 100	230 ms	2644 KiB

transfer

#include "transfer.h"
#include <bits/stdc++.h>
using namespace std;


vector<int> get_attachment(vector<int>src){
    if(src.size()<=3){
        int n=src.size();
        for(int i=0;i<n;i++)src.push_back(src[i]);
        return src;
    }

    int n =src.size();
    int p=7;
    if(n>63)
        p=9;

    vector<int>ret(p);

    int sz=ret.size();
    for(int i=0;i<sz;i++){
        for(int j=0;j<n;j+=2*(1<<i)){
            for(int k=0;k<(1<<i);k++)
                if(j+k<n)
                    ret[i]^=src[j+k];
        }
    }

    return ret;
}

vector<int> retrieve(vector<int>data){
    vector<int>ret;
    if(data.size()<=9){
        int n=data.size();
        for(int i=0;i<n/3;i++){
            ret.push_back(((data[i]+data[n/3+i]+data[2*n/3+i])>=2)?1:0);
        }
    }else{

        /**for(int i=0;i<data.size();i++)cout<<data[i]<<' ';
        cout<<'\n';*/
        int p=7;
        if(data.size()>70)
            p=9;
        int n=data.size()-p;
        int xo=0;
        for(int i=0;i<n;i++) xo^=data[i];
        vector<int>ret;
        if(xo==data[data.size()-1]){
            for(int i=0;i<n;i++){
                ret.push_back(data[i]);
            }
            return  ret;
        }
        int cr=p-1;
        int l=0;

        while(cr>=0&&l<n){
            int i=cr;
            xo=0;
            for(int j=0;j<n;j+=2*(1<<i)){
                for(int k=0;k<(1<<i);k++)
                    if(j+k<n)
                        xo^=data[j+k];
            }

            if(xo==data[n+cr])
                l+=(1<<cr);
            if(cr==0)data[l]=!data[l];
            ///cout<<l<<' '<<xo<<'\n';

            cr--;
        }
        for(int i=0;i<n;i++){
                ret.push_back(data[i]);
        }
        return  ret;


    }
    return ret;
}

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