Submission #357877

#	Time	Username	Problem	Language	Result	Execution time	Memory
357877		Ahmad_Hasan	Data Transfer (IOI19_transfer)	C++17	0 / 100	18 ms	2604 KiB

transfer

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

vector<int> get_attachment(vector<int>src){
    if(src.size()<=30)
        return src;
    long long p=31;
    long long mod=1e9+7;
    long long ppow=1ll;
    long long hsh=0ll;
    int n=src.size();
    for(int i=0;i<n;i++){
        hsh+=src[i]*ppow;
        hsh%=mod;
        ppow*=p;
        ppow%=mod;
    }
    vector<int>ret(30);
    for(int i=0;i<30;i++)ret[i]=!!(hsh&(1<<i));

    return ret;
}

vector<int> retrieve(vector<int>data){
    vector<int>ret;
    if(data.size()<=60){
        int n=data.size();
        for(int i=n/2;i<n;i++)
            ret.push_back(data[i]);
    }else{

        long long p=31;
        long long mod=1e9+7;
        long long ppow=1ll;
        long long hsh=0ll;
        int n=data.size()-30;
        vector<int>ret;
        for(int i=0;i<n;i++){
            hsh+=data[i]*ppow;
            hsh%=mod;
            ppow*=p;
            ppow%=mod;
        }
        int f=0;
        for(int i=n;i<data.size();i++){
            if(data[i]!=!!(hsh&(1<<(i-n))))
                f=1;
        }
        if(!f){
            for(int i=0;i<n;i++){
                ret.push_back(data[i]);
            }
            return ret;
        }
        for(int i=0;i<n;i++){
            data[i]=!data[i];

            p=31;
            mod=1e9+7;
            ppow=1ll;
            hsh=0ll;
            for(int i=0;i<n;i++){
                hsh+=data[i]*ppow;
                hsh%=mod;
                ppow*=p;
                ppow%=mod;
            }
            int f=0;
            for(int i=n;i<data.size();i++){
                if(data[i]!=!!(hsh&(1<<(i-n))))
                    f=1;
            }
            if(!f){
                for(int i=0;i<n;i++){
                    ret.push_back(data[i]);
                }
                return ret;
            }

            data[i]=!data[i];
        }

    }
    return ret;
}

Compilation message (stderr)

transfer.cpp: In function 'std::vector<int> retrieve(std::vector<int>)':
transfer.cpp:46:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i=n;i<data.size();i++){
      |                     ~^~~~~~~~~~~~
transfer.cpp:70:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |             for(int i=n;i<data.size();i++){
      |                         ~^~~~~~~~~~~~

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