제출 #291957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
291957		Autoratch	Data Transfer (IOI19_transfer)	C++14	80 / 100	247 ms	2828 KiB

transfer

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

int ret[10],mxk,n;
vector<int> s;

void send(int l,int r,int k)
{
    if(l==r) return;
    mxk = max(mxk,k);
    int m = (l+r)/2,v = 0;
    for(int i = l;i <= m;i++) v^=s[i];
    ret[k]^=v;
    send(l,m,k+1),send(m+1,r,k+1);
}

vector<int> get_attachment(vector<int> source)
{
    s = source;
    for(int i = 0;i < 10;i++) ret[i] = 0;
    mxk = 0;
    send(0,source.size()-1,0);
    vector<int> tmp;
    for(int i = 0;i <= mxk;i++) tmp.push_back(ret[i]);
    int all = 0;
    for(int x : source) all^=x;
    tmp.push_back(all),tmp.push_back(all);
    return tmp;
}

int solve(int l,int r,int k)
{
    if(l==r) return l;
    int m = (l+r)/2;
    if(ret[k]!=s[n+k]) return solve(l,m,k+1);
    else return solve(m+1,r,k+1);
}

vector<int> retrieve(vector<int> data)
{
    if(data.size()>200) n = 255;
    else n = 63;
    int all = 0;
    for(int i = 0;i < n;i++) all^=data[i];
    if(data[data.size()-1]!=data[data.size()-2] or data.back()==all)
    {
        vector<int> tmp;
        for(int i = 0;i < n;i++) tmp.push_back(data[i]);
        return tmp;
    }
    for(int i = 0;i < 10;i++) ret[i] = 0;
    mxk = 0;
    s = data;
    send(0,n-1,0);
    int idx = solve(0,n-1,0);
    vector<int> tmp;
    for(int i = 0;i < n;i++) tmp.push_back(data[i]);
    tmp[idx]^=1;
    return tmp;
}

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