oj.uz

답안 #628434

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
628434 2022-08-13T11:56:22 Z abcvuitunggio Hotter Colder (IOI10_hottercolder) C++17
81 / 100
 8849 ms 8108 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
map <pair <int, int>, int> mp,mp2;
int HC(int N){
    mp.clear();
    mp2.clear();
    int l=1,r=N,kq=N,val;
    int last=N;
    val=Guess(N);
    while (l<r){
        if (mp2.count({l,r})){
            int lo=max(1,l+r-N),hi=min(N,l+r-1);
            last=(lo-1<N-hi?hi:lo);
            val=Guess(last);
        }
        mp2[{l,r}]=1;
        int mid=l+r-last;
      	mid=max(mid,1);
      	mid=min(mid,N);
        val=(mp.count({last,mid})?mp[{last,mid}]:Guess(mid));
        int ch=(mp.count({last,mid}));
        mp[{last,mid}]=val;
        mp[{mid,last}]=-val;
        if (val==0)
            return (mid+last)/2;
        if (val==1){
            if (last<mid)
                l=(last+mid+1)/2;
            else{
                r=(last+mid-1)/2;
                kq=r;
            }
            if (!ch)
                last=mid;
            continue;
        }
        if (last<mid){
            r=(last+mid-1)/2;
            kq=r;
        }
        else
            l=(last+mid+1)/2;
        if (!ch)
            last=mid;
    }
    return kq;
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 243 ms 1280 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 252 ms 1236 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 1280 KB Output is correct

Subtask #4
6.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 8849 ms 8108 KB Output is partially correct - alpha = 0.250000000000