Here’s the code for binary search in rows with large matrix and cost optimizations.
#include <bits/stdc++.h>
using namespace std;
int mat[61][61];
map<pair<pair<int,int>,pair<int,int> >,int> askedValueStorer;
bool chooseLeft[61];
int response(int r1,int c1,int r2,int c2){
if(askedValueStorer.find({{r1,c1},{r2,c2}})!=askedValueStorer.end()){
return askedValueStorer[{{r1,c1},{r2,c2}}];
}
cout << "1 " << r1 << ' ' << c1 << ' ' << r2 << ' ' << c2 << '\n';
int x;
cin >> x;
askedValueStorer[{{r1,c1},{r2,c2}}] = x;
return x;
}
int outputMatrix(){
cout << 2 << '\n';
for(int i=1;i<=60;i++){
for(int j=1;j<=60;j++){
cout << mat[i][j];
cout << (j==60 ? '\n' : ' ');
}
}
int x;
cin >> x;
return x;
}
int askQuery(int r1,int c1,int r2,int c2,int typeQuery){
int resp;
int CountforLeft,CountforRight;
if(typeQuery == 1){
resp = response(1,c1,r2,c2);
CountforRight = resp;
}
else{
int a = response(1,c1,60,c2);
int b = response(r2+1,c1,60,c2);
resp = a-b;
askedValueStorer[{{1,c1},{r2,c2}}] = a-b;
CountforRight = b;
assert(resp>=0);
}
if(r2>30 && c1!=1 && chooseLeft[c1]==false){
CountforLeft = askedValueStorer[{{1,1},{r2,60}}] - CountforRight;
if(CountforLeft > CountforRight){
for(int i=c1+1;i<=60;i++){
chooseLeft[i] = true;
}
}
}
if(r2>30 && c2!=60 && chooseLeft[c2]==true){
CountforLeft = CountforRight;
CountforRight = askedValueStorer[{{1,1},{r2,60}}] - CountforLeft;
if(CountforLeft < CountforRight){
for(int i=c2;i>0;i--){
chooseLeft[i] = false;
}
}
}
int prevRowsum = 0;
for(int i=1;i<r1;i++){
for(int j=c1;j<=c2;j++){
prevRowsum+=mat[i][j];
}
}
resp -=prevRowsum;
return resp;
}
void fillzeros(int r,int c1,int c2){
for(int c=c1;c<=c2;c++){
mat[r][c] = 0;
}
}
void fillones(int r,int c1,int c2){
for(int c=c1;c<=c2;c++){
mat[r][c] = 1;
}
}
map<pair<int,int>,int> interval_sum;
void bss(int l,int r,int rowsum,int i,int TYPE,bool isSimpleProcess){
if(l>r)return;
else if(l==r){
mat[i][l] = interval_sum[{l,r}];
}
else{
int mid = (l+r)/2;
int leftQ,rightQ;
bool chooseit = isSimpleProcess ? (mid > 30) : chooseLeft[mid];
if(chooseit)leftQ = askQuery(i,1,i,mid,TYPE);
else leftQ = rowsum - askQuery(i,mid+1,i,60,TYPE);
int tempsum = 0;
for(int k=0;k<l;k++){
assert(mat[i][k]!=-1);
tempsum+=mat[i][k];
}
leftQ-=tempsum;
rightQ = interval_sum[{l,r}]-leftQ;
interval_sum[{l,mid}] = leftQ;
interval_sum[{mid+1,r}] = rightQ;
if(leftQ==0){
fillzeros(i,l,mid);
}
else if(leftQ==(mid-l+1)){
fillones(i,l,mid);
}
else{
bss(l,mid,rowsum,i,TYPE,isSimpleProcess);
}
if(rightQ==0){
fillzeros(i,mid+1,r);
}
else if(rightQ==(r-(mid+1)+1)){
fillones(i,mid+1,r);
}
else{
bss(mid+1,r,rowsum,i,TYPE,isSimpleProcess);
}
}
}
void process_4(){
for(int i=1;i<=60;i++){
int TYPE = (i>30 ? 1 : 2);
//cout << TYPE;
int rowsum = askQuery(i,1,i,60,TYPE);
//OnesinRow[i] = rowsum;
for(int j=1;j<=60;j++)chooseLeft[j] = (j<=30) ? false : true;
if(rowsum==0){
fillzeros(i,1,60);
}
else{
interval_sum.clear();
interval_sum[{1,60}] = rowsum;
bss(1,60,rowsum,i,TYPE,false);
}
}
}
int main() {
int t;
cin >> t;
while(t--){
askedValueStorer.clear();
for(int i=1;i<=60;i++){
for(int j=1;j<=60;j++){
mat[i][j] = -1;
}
}
int n,p;
cin >> n >> p;
process_4();
int res = outputMatrix();
if(res==-1)break;
}
}
Got 77 points in Div 2.