Submission #1289942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289942		muhammad-mutahir	Cave (IOI13_cave)	C++20	0 / 100	229 ms	532 KiB

cave

#include "cave.h"
#include <bits/stdc++.h>
using namespace std;

#define print(l) for(auto i:l) cout<<i<<" ";cout<<endl;
#define input(t,l,n) vector<t>l(n);for(int i = 0;i<n;i++)cin>>l[i];
// #define int long long
#define pb push_back
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define all(l) l.begin(),l.end()
#define pii pair<int,int>
#define fi first
#define se second

const int M = 1e9+7;
const int inf = 1e18;


int bp(int x, int y, int p){
    int res = 1;
    x = x % p;
    while (y > 0) {
 
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
 
int MI(int n, int p){
    return bp(n, p - 2, p);
}
int mul(int x,int y, int p){
    return x * 1ull * y % p;
}
int di(int x,int y, int p){
    return mul(x, MI(y, p), p);
}


int n , m , k , q;



// map<pair<int,int>,int>ob;
// int tryCombination(int K[]){
	// cout<<"? ";
	// for(int i = 0;i<n;i++){
		// cout<<K[i]<<" "; 
	// }
	// cout<<endl;
	// int yu;
	// cin>>yu;
	// return yu;
// }
// 
// void answer(int A[],int B[]){
	// cout<<"! ";
	// for(int i = 0;i<n;i++){
		// cout<<A[i]<<" ";
	// }
	// cout<<endl;
	// cout<<"! ";
	// for(int i = 0;i<n;i++){
		// cout<<B[i]<<" ";
	// }
	// cout<<endl;
// }

void exploreCave(int N) {
    int cf[N];
    n = N;
    int ans[N];
    for(int i = 0;i<N;i++){
    	cf[i] = -1;
    }
    for(int i = 0;i<N;i++){
    	// vector<int>tc
    	int cd;
    	int k[N];
    	for(int j =0 ;j<N;j++){
    		k[j] = cf[j];
    		if(cf[j] == -1){
    			k[j] = 1;
    		}
    	}
    	
    	cd = tryCombination(k);

    	if(cd >= i+1 or cd == -1){
    		cd = 1;
    	}
    	else{
    		cd = 0;
    	}
    	// cout<<"state "<<i<<" "<<cd<<endl;
    	
    	int l = -1;
    	int r = N;
    	
    	while(r-l>1){
    		int m = (l+r)/2;
	    	int k[N];
	    	for(int j =0 ;j < m;j++){
	    		k[j] = cf[j];
	    		if(cf[j] == -1){
	    			k[j] = cd;
	    		}
	    	}
	    	for(int j =m ;j < n;j++){
	    		k[j] = cf[j];
	    		if(cf[j] == -1){
	    			k[j] = !cd;
	    		}
	    	}
	    	
    		int kk = tryCombination(k);
    		// cout<<i<<" "<<l<<" "<<r<<" "<<m<<" "<<kk<<" "<<endl;
    		
    		if(kk >= i+1 or kk == -1){
    			r = m;
    		}
    		else{
    			l = m;
    		}
    	}
    	// cout<<"position "<<i<<" "<<r<<endl;
    	ans[r] = i;
    	cf[r] = cd;
    }
    answer(cf,ans);
}


// signed main(){
    // ios::sync_with_stdio(0);//DO NOT USE IN INTERACTIVE
    // cin.tie(0), cout.tie(0);
    // cout << fixed<<setprecision(9);
    // int n;
    // cin>>n;
    // exploreCave(n);
// 
// }

Compilation message (stderr)

cave.cpp:16:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const int inf = 1e18;
      |                 ^~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 13
• Subtask 3: 0 / 21
• Subtask 4: 0 / 30
• Subtask 5: 0 / 24