Submission #1305752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305752		hackstar	Hack (APIO25_hack)	C++20	56.60 / 100	148 ms	2808 KiB

hack

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

using namespace std;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define ll long long

// collisions()

int cnst=7001;

int hack(){
        vector<ll>copy(cnst-1);
        iota(all(copy),1);
        ll l=1;
        int r=142836;
        int total=0;
        ll ans=0;
		    map<vector<ll>,int>cache;
        while(l<=r){
                int m=l+r>>1;
                vector<ll>cur=copy;
                for(int i=l;i<=m;i++){
                        cur.emplace_back(i*cnst);
                }
                // cout<<total<<'\n';
                total+=cur.size();
        				int curr;
        				if(cache.count(cur))
        						curr=cache[cur];
        				else
        				{
        						curr=collisions(cur);
        						cache[cur]=curr;
        				}
                if(curr){
                        // ans=m;
                        r=m-1;
                }
                else{
                        ans=m;
                        l=m+1;
                }
        }
        // cout<<ans<<'\n';
        if(!ans){
                int n=1;
                while(n++){
                        total+=2;
                        if(collisions({1,n+1})){
                                return n;
                        }
                }
                return -1;
        }
        // cout<<total<<'\n';
        // cout<<x<<'\n';
	for(int i=max(2ll,cnst*ans);i<cnst*(ans+1);i++){
		if(collisions({1,i+1})){
			return i;
		}
	}
        return -1;
}

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