Submission #248955

#	Time	Username	Problem	Language	Result	Execution time	Memory
248955		Dilshod_Imomov	Cave (IOI13_cave)	C++17	0 / 100	3 ms	640 KiB

cave

# include "cave.h"
# include <bits/stdc++.h>
using namespace std;
/*
int tryCombination(vector < int > S ) {
	counts++;
	for ( int i = 0; i < n; i++ ) {
		if ( S[door[i].first] == door[i].second ) {
			continue;
		}
		return i;
	}
	return -1;
}

void answer( vector < int > S, vector < int > D ) {
	for ( int i = 0; i < n; i++ ) {
		int dr = D[i], t = S[i];
		cout << S[i] << ' ' << D[i] << '\n';
		if ( door[dr].first != i || door[dr].second != t ) {
			// cout << "Wrong Answer" << '\n';
			// exit(0);
		}
	}
	cout << "Accepted with " << counts << " counts.\n";
	exit(0);
}
*/
auto create( vector < int > vc ) {
	int n = vc.size();
	for ( int i = 0; i < (int)vc.size(); i++ ) {
		if ( vc[i] == -1 ) {
			vc[i] = 1;
		}
	}
	int drs[n];
	for ( int i = 0; i < n; i++ ) {
		drs[i] = vc[i];
	}
	return drs;
} 

int can( vector < int > doors, int mid, int l, int r  ) {
	int cnt = mid, cntl = 0, n = doors.size();
	for ( int i = 0; i < n; i++ ) {
		if ( doors[i] != -1 ) {
			continue;
		}
		if ( cntl < l ) {
			doors[i] = 1;
			cntl++;
			continue;
		}
		if ( cnt ) {
			doors[i] = 0;
			cnt--;
		}
		else {
			doors[i] = 1;
		}
	}
	int drs[n] = {};
	for ( int i = 0; i < n; i++ ) {
		drs[i] = doors[i];
	}
	return tryCombination(drs);
}

int find( vector < int > doors, int l ) {
	int cnt = 0, n = doors.size();
	for ( int i = 0; i < n; i++ ) {
		if ( doors[i] != -1 ) {
			continue;
		}
		if ( cnt == l ) {
			return i;
		}
		cnt++;
	}
	return 0;
}

void exploreCave(int N) {
	int n = N;
	vector < int > doors(N, -1), S(N), D(N);
	int cnt = N - 1; 
	for ( int i = 0; i < n; i++ ) {
		int fdoor = tryCombination( create(doors) );
		int ans = 0;
		if ( fdoor != i ) {
			ans = 1;
		}
		int l = 0, r = cnt, mid;
		while ( l < r ) {
			mid = (l + r) / 2;
			int x = can( doors, mid - l + 1, l, r );
			if ( x != i ) {
				if ( ans == 0 ) {
					r = mid;
				}
				else {
					l = mid + 1;
				}
			}
			else {
				if ( ans == 0 ) {
					l = mid + 1;
				}
				else {
					r = mid;
				}
			}
		}
		int x = find(doors, l);
		doors[x] = ans;
		S[x] = ans;
		D[x] = i;
		cnt--;
	}
	int SS[n], DD[n];
	for ( int i = 0; i < n; i++ ) {
		SS[i] = S[i];
		DD[i] = D[i];
	}
	answer(SS, DD);
}
/*
int main()
{
	input();
	exploreCave(n);
	return 0;
}
*/

Compilation message (stderr)

cave.cpp: In function 'auto create(std::vector<int>)':
cave.cpp:36:6: warning: address of local variable 'drs' returned [-Wreturn-local-addr]
  int drs[n];
      ^~~

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