Idea: To be updated next week. I am a little busy now, so please do not downvote me. If you are interested or confused, you can comment or chat with me.
My submission: submission
My code here:
#include<bits/stdc++.h>
using namespace std;
#define BIT(x, i) (((x) & (1 << (i))) >> (i))
#define DEBUG 0
#define DEBUG_INTERACTIVE 0
constexpr int C = 11, MAXN=2005; //Since N <= 2000, nim number <= 2000, so we only need to scan 1<<0 to 1<<11.
int n, l, r;
int sg[MAXN]; //sg number for 1-n
int f[MAXN][MAXN];
//f[i][j] If we want to get sg number j from [1, i], where should I cut?
//For example, if sg(i) = 4 and get sg number 3 after cutting [j, k], then f[i][3] = j;
int nim(const vector<int>& v, int* index, int* value_after_change){
//input:
//v: A vector of stones.
//index and value_after_change: If the XOR sum of v is 0, then index remains unchanged. we modify v[*index]
//to *value_after_change to guarantee that the XOR sum of v after modification is 0.
//Output:
//The XOR sum of v (current v)
//Example1:
//vector<int> v = {1, 4, 3};
//int index, value_after_change;
//int value = nim(v, &index, &value_after_change);
//cout << value << " " << index << " " << value_after_change << "\n"; //6 1 2
//value = 1^4^3 = 6;
//change 4->2, 1^2^3=0
//Example2:
//vector<int> v = {1, 2, 3};
//int index, value_after_change;
//int value = nim(v, &index, &value_after_change);
//cout << value << " " << index << " " << value_after_change << "\n"; //0 32763 -1204770170
//1^2^3 = 0. You cannot modify any number, then index and value_after_change are uninitialized random numbers (may not be 32763 -1204770170)
int sz = (int)v.size();
vector<int> ones[C+1];
int res = 0;
for(int b = 0; b <= C; ++b){
for(int i = 0; i < sz; ++i){
if(BIT(v[i], b)){
ones[b].push_back(i);
}
if(!b) res ^= v[i]; //Calculate the XOR sum, also known as the Nim sum. Remember only xor once.
}
}
if(res == 0) return res;
bool flipped = false;
*value_after_change = 0;
int choosed = -1; //FIX
for(int b = C; b >= 0; --b){
if(BIT(res, b)){
if(!flipped){
choosed = b;//FIX
flipped = true;
*index = ones[b][0]; //Never overflows, think out why?
}else{
*value_after_change += ((!BIT(v[*index], b)) << b);
}
}else if(flipped){
(*value_after_change) += (v[*index] & (1 << b));
}
}
for(int i = choosed+1; i <= C; ++i){ //FIX
*value_after_change += (v[*index] & (1<<i)); //FIX
} //FIX
return res;
}
void sgdp(bool debug){ //dynamic programming to calculate sprague-grundy numbers
//The following code is unnecessary because sg is global variable.
//for(int i = 0; i <= l-1; ++i){
// sg[i] = 0; //Nowhere to fetch, have to lose, sg number is 0.
//}
for(int len = l; len <= n; ++len){
set<int> mex;
for(int i = 1; i <= len-l+1; ++i){
//We fetch [i, i+l-1]
int sgleft = sg[i-1]; //sg[0] is defined
int sgright = sg[len-i-l+1];
int sgall = sgleft ^ sgright; //Grundy theorem!!!
f[len][sgall] = i;
mex.insert(sgall);
}
int t = 0;
while(mex.count(t)) ++t;
sg[len] = t;
}
//DEBUG
if(!debug) return;
for(int len = l; len <= n; ++len){
printf("sg[%d]==%d\n", len, sg[len]);
for(int k = 0; k < sg[len]; ++k){
printf("f[%d][%d]==%d\n", len, k, f[len][k]);
}
printf("\n");
}
}
int main(int argc, char** argv){
if(DEBUG){
//freopen(argc == 1?"test1.txt":argv[1], "r", stdin);
}else if(DEBUG_INTERACTIVE){
; //DO NOTHING
}else{
cin.tie(0) -> sync_with_stdio(0);
}
cin >> n >> l >> r;
//The first case: r is large enough:
//Prefix (length <= l-1), Middle (length==r), Appendix (length <= l-1)
int a = 1, b = 1; //Ready to receive moves from the AI.
if(r + 2 * l - 2 >= n && l + r - 1 <= n){
//Killer move
cout << "First" << endl;
cout << l << " " << r << endl;
cin >> a >> b;
//AI fails.
return 0;
}
//The second case: Mimicking
if(l != r || n % 2 == l % 2){
//According to the tutorial, we can use the first move to separate [1-n] into two symmetric parts.
int tmp = r;
while((n - tmp) % 2) --tmp; //Don't be scary, it is O(1).
//Such tmp is always valid. If l != r, one of {r-1, r} is ok. Otherwise if l==r, r is eligible for tmp.
int interval = (n - tmp)/2;
cout << "First" << endl;
cout << interval+1 << " " << tmp << endl;
//Here we cut the interval [1, n] into two parts: [1, interval], [interval+tmp+1, n]
//interval == n-interval-tmp.
while(a || b){
cin >> a >> b;
if(a == 0 && b == 0){
return 0;
}
if(a <= interval){
//cout << a+interval+tmp << " " << b+interval+tmp << endl; //BUG. The second parameter is the LENGTH, not the ENDING POINT.
cout << a+interval+tmp << " " << b << endl;
}else{
//cout << a-interval-tmp << " " << b-interval-tmp << endl; //BUG. The second parameter is the LENGTH, not the ENDING POINT.
cout << a-interval-tmp << " " << b << endl;
}
}
return 0;
}
//The third case: l == r && n % 2 != l % 2. We cannot mimick. No matter where we choose [x, x+y-1], We cannot separate [1, n]
sgdp(DEBUG || DEBUG_INTERACTIVE);
set<pair<int, int>> intervals = {{1, n}};
bool turn = true, initial = true;
if(sg[n] == 0) {
cout << "Second" << endl;
turn = false;
}else{
cout << "First" << endl;
}
while(a || b){
if(turn){
if(!initial){
//Use {a, a+b-1} to separate intervals
pair<int, int> ab = {a, a+b-1};
auto it = intervals.upper_bound(ab);
if(it==intervals.end() || it->first > ab.first) it = prev(it);//Always valid
int fi = it->first, se = it->second;
if(DEBUG || DEBUG_INTERACTIVE) {
for(auto pa: intervals){
cout << "[Intervals1]" << pa.first << " " << pa.second << "\n";
}
printf("DEBUG1: it=={%d, %d}, ab=={%d, %d}\n", fi, se, ab.first, ab.second);
}
if(ab.first-1 >= it->first){
intervals.insert({it->first, ab.first-1});
}
if(ab.second+1 <= it->second){
intervals.insert({ab.second+1, it->second});
}
intervals.erase({fi, se});
}
int isz = (int)intervals.size();
vector<int> v(isz);
vector<pair<int, int>> vp(intervals.begin(), intervals.end()); //This is bad, but convenient...
if(DEBUG || DEBUG_INTERACTIVE) {
for(int i = 0; i < isz; ++i) {
printf("DEBUG_PLACE1 <SG should NOT be 0>: vp[%d]=={%d, %d}, gr==%d\n", i, vp[i].first, vp[i].second, sg[vp[i].second - vp[i].first + 1]);
}
}
for(int i = 0; i < isz; ++i){
v[i] = sg[vp[i].second - vp[i].first + 1];
}
int index = -1, value_after_change = -1;
nim(v, &index, &value_after_change); //I will never make nim(v, &index, &value_after_change)==0 here!
int cutplace = f[vp[index].second - vp[index].first + 1][value_after_change];
if(DEBUG || DEBUG_INTERACTIVE) {
for(int i = 0; i < isz; ++i) printf("v[%d]==%d, index==%d, value_after_change==%d\n", i, v[i], index, value_after_change);
cout << vp[index].first + cutplace - 1 << " " << l << " AI" << endl;
}
else cout << vp[index].first + cutplace - 1 << " " << l << endl;
//Also remember to separate intervals!
pair<int, int> ab = {vp[index].first + cutplace - 1, vp[index].first + cutplace + l - 2};
auto it = intervals.upper_bound(ab); //Always valid
if(it==intervals.end() || it->first > ab.first) it = prev(it);
int fi = it->first, se = it->second;
if(DEBUG || DEBUG_INTERACTIVE) {
for(auto pa: intervals){
cout << "[Intervals2]" << pa.first << " " << pa.second << "\n";
}
printf("DEBUG2: it=={%d, %d}, ab=={%d, %d}\n", fi, se, ab.first, ab.second);
}
if(ab.first-1 >= it->first){
intervals.insert({it->first, ab.first-1});
}
if(ab.second+1 <= it->second){
intervals.insert({ab.second+1, it->second});
}
intervals.erase({fi, se});
if(DEBUG || DEBUG_INTERACTIVE) {
int i = 0;
for(pair<int, int> pa: intervals) {
printf("DEBUG_PLACE2 <SG should be 0>: i==%d, {%d, %d}, sg==%d\n", i, pa.first, pa.second, sg[pa.second-pa.first+1]);
++i;
}
}
}else{
cin >> a >> b;
}
turn = !turn;
initial = false;
}
if(a == -1 && b == -1) return 0;
}
Acknowledgment: ABalobanov, Nyaan.