oj.uz

Submission #77297

# Submission time Handle Problem Language Result Execution time Memory
77297 2018-09-24T20:05:30 Z toreto_back Highway Tolls (IOI18_highway) C++14
0 / 100
 40 ms 604 KB 
#include "highway.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef double D;
const ll mod=1e9+7;
const ll inf=(1ll<<61);
const int MX=3e5+9;


vector<int>w;
int m;
void init(int x){
    for(int j=0;j<m;j++)w[j]=x;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int l=0,r=N-1,M=U.size(),n=N;
    int q=99;m=M;
    for(int i=0;i<m;i++)w.push_back(0);
    ll c=ask(w);
    int len=c/A;
    while(r-l+1>2*len && r-l+1-len+1>q){
        int mid=(l+r)/2;
        init(0);
        for(int i=l;i<mid;i++)w[i]=1;
        ll c1=ask(w);q--;
        if(c1==c){
            l=max(0,mid-len+1);
        }
        else r=min(mid+len-1,n-1);
    }
    init(1);
    for(int i=l;i<(l+r)/2;i++)w[i]=0;
    ll c1=ask(w);q--;
    if(c1==c){
        r=(l+r)/2+1;
    }
    else{
        c=c1;
        ll d=len,a=A,b=B;
        ll xb=(c-d*a)/(b-a);
        ll xa=(c-(b*((c-d*a)/(b-a))))/a;
        xa=(l+r)/2 - xa;
        answer(xa,xa+len);
        return;
    }
    for(int i=l;;i++){
        init(1);
        for(int j=i;j<len+i;j++)w[j]=0;
        ll c1=ask(w);
        if(c1==c){
            answer(i,i+len);
            break;
        }
    }
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:43:12: warning: unused variable 'xb' [-Wunused-variable]
         ll xb=(c-d*a)/(b-a);
            ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 560 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 536 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 604 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -