oj.uz

Submission #341966

# Submission time Handle Problem Language Result Execution time Memory
341966 2020-12-31T19:46:03 Z limabeans Colors (BOI20_colors) C++17
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;
const ll inf = 1e18;




vector<bool> a;

int ask(ll x) {
    a[x] = true;
    cout<<"? "<<x<<endl;
    int res;
    cin>>res;
    return res;
}

// 1 -> n -> 2 -> n-1 -> 3 ...
// test gaps n-1, n-2, n-3, ...
void solve(ll n) {
    assert(n<=1000);
    a.clear();
    a.resize(n+10, false);
    
    ll c = n;

    ll lo = 1;
    ll hi = n;
    ask(lo++);
    bool flag = true;
    for (ll gap=n-1; gap>=1; gap--) {
	if (flag) {
	    if (ask(hi--)) {
		c = gap;
	    }
	} else {
	    if (ask(lo++)) {
		c = gap;
	    }
	}

	flag = !flag;
    }

    cout<<"= "<<c<<endl;
}



void solve2(ll n) {
    assert(n<=1000);
    a.clear();
    a.resize(n+10, false);
    deque<ll> qq;
    ll lo = 1;
    ll hi = n;
    for (ll i=0; i<n; i++) {
	if (i%2==0) {
	    qq.push_back(lo++);
	} else {
	    qq.push_back(hi--);
	}
    }

    ll c = n;
    
    ll mid = (1+n)/2;
    ll i = 0;
    while (i+1<n && abs(qq[i]-qq[i+1])!=mid) i++;
    assert(i+1<n);
    ask(qq[i]);

    
    // smaller --->
    if (ask(qq[i+1])) {
	c = abs(qq[i]-qq[i+1]);
	i += 2;
	for (; i<n; i++) {
	    if (ask(qq[i])) {
		c = abs(qq[i-1]-qq[i]);
	    }
	}
    } else {
	// c > mid
	set<int> todo;
	for (int g=mid+1; g<n; g++) {
	    todo.insert(g);
	}
	
	// ... | qq[i-1] |, qq[i], qq[i+1],..
	
	--i;
	
	ask(qq[i]);
	ll last = qq[i];
	--i;
	
	for (; i>=0; i--) {
	    if (ask(qq[i])) {
		c = min(c, abs(qq[i]-qq[i+1]));
	    }
	    todo.erase(abs(qq[i]-qq[i+1]));
	    last = qq[i];
	}


	for (ll g: todo) {
	    // watch(g);
	    // watch(last);
	    // watch(last-g);
	    // watch(last+g);
	    
	    if (last-g>=1 && !a[last-g]) {
		if (ask(last-g)) {
		    c = min(c, g);
		    last = last-g;
		}
	    } else if (last+g<=n && !a[last+g]) {
		if (ask(last+g)) {
		    c = min(c, g);
		    last = last+g;
		}
		
	    } else {
		// try all
		for (ll i=1; i+g<=n; i++) {
		    if (!a[i] && !a[i+g]) {
			ask(a[i]);
			if (ask(a[i+g])) {
			    c = min(c, g);
			}
			last = i+g;
		    }
		}
	    }
	}
    }

    cout<<"= "<<c<<endl;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    int t; cin>>t;
    while (t--) {
	ll n;
	cin>>n;
	if (n<=64) {
	    solve(n);
	} else {
	    solve2(n);
	}
    }
    
    
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1 ms 364 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -