제출 #1246392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246392		radaiosm7	Hack (APIO25_hack)	C++20	63.50 / 100	178 ms	3336 KiB

hack

//chockolateman credit
#include<bits/stdc++.h>
#include <vector>
#include "hack.h"

using namespace std;

const long long S = 31623;


vector<long long> nums;
vector<long long> temp;

long long query_pair(int x)
{
    temp.clear();
    temp.push_back(1);
    temp.push_back(1+x);
    return collisions(temp);
}

int hack(){
    temp.clear();
    if(nums.empty())
    {
        nums.push_back(0); //make it 1-indexed
        for(int i = 1 ; i <= S ; i++)
            nums.push_back(nums.back() + 1);
        for(int i = 1 ; i <= S ; i++)
            nums.push_back(nums.back() + S);
    }
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(nums.begin()+1, nums.end(), rng);
    vector<long long> x;
    vector<long long> xf,xs,xf1,xf2,xs1,xs2,y;
    for(auto k : nums)
        if(k != 0)
            x.push_back(k);
    bool split = false;

    while ((!split && (int)x.size() > 2) || (split && ((int)xf.size() > 1 || (int)xs.size() > 1))) {
        int m;
        if (!split) {
            m = (int)x.size();
            xf.clear();
            xs.clear();
            for (int i=0; i < m/2; ++i) xf.push_back(x[i]);
            for (int i=m/2; i < m; ++i) xs.push_back(x[i]);

            if (collisions(xf) != 0) {
                x = xf;
                continue;
            }

            if (collisions(xs) != 0) {
                x = xs;
                continue;
            }
        }
    
        split = true;
        xf1.clear();
        xf2.clear();
        m = (int)xf.size();
        for (int i=0; i < m/2; ++i) xf1.push_back(xf[i]);
        for (int i=m/2; i < m; ++i) xf2.push_back(xf[i]);
        
        xs1.clear();
        xs2.clear();
        m = (int)xs.size();
        for (int i=0; i < m/2; ++i) xs1.push_back(xs[i]);
        for (int i=m/2; i < m; ++i) xs2.push_back(xs[i]);

        y.clear();
        for (auto el : xf) y.push_back(el);
        for (auto el : xs1) y.push_back(el);

        if (collisions(y) != 0) {
            y.clear();
            xs = xs1;
            for (auto el : xf1) y.push_back(el);
            for (auto el : xs1) y.push_back(el);
            if (collisions(y) != 0) xf = xf1;
            else xf = xf2;
            continue;
        }

        y.clear();
        for (auto el : xf1) y.push_back(el);
        for (auto el : xs2) y.push_back(el);
        if (collisions(y) != 0) {
            xf = xf1;
            xs = xs2;
            continue;
        }

        y.clear();
        for (auto el : xf2) y.push_back(el);
        for (auto el : xs2) y.push_back(el);
        xf = xf2;
        xs = xs2;
    }

    long long diff;
    if (!split) diff = llabs(x[1]-x[0]);
    else diff = llabs(xs[0]-xf[0]);

    vector<long long> di;
        for (long long d=2LL; d*d <= diff; ++d) {
        if (diff % d == 0LL) {
            di.push_back(d);
            di.push_back(diff/d);
        }
    }
    di.push_back(diff);
    sort(di.begin(), di.end());
    int dsz = (int)di.size();

    for (int p=0; p < dsz; ++p) {
        vector<long long> v;
        v.push_back(1LL);
        v.push_back(di[p]+1LL);
        if (collisions(v) == 1) return di[p];
    }
}

컴파일 시 표준 에러 (stderr) 메시지

hack.cpp: In function 'int hack()':
hack.cpp:125:1: warning: control reaches end of non-void function [-Wreturn-type]
  125 | }
      | ^

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 38.5267 / 75