AtCoder Regular Contest 142

A Needless to say ,C After the question, you won't ...

B - Unbalanced Squares

Carelessness ：

Construct a n Order matrix （ Elements from 1~n^2）, For each element of the matrix , The number of elements around it greater than it and the number of elements less than it cannot be equal .

Ideas ：
It took me more than 20 minutes to get my idea ... The brain is getting worse .

My thoughts ：

If the matrix is made directly from small to large ：

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16

Obviously not . But take a closer look , If you change the order of the elements in each row , It may be hopeful （ It's better than reconstructing it all ）. Each element of the first and last lines is conditional . For some elements in the middle line , If it's on the edge , The next two elements are smaller , The above two elements are larger than it , So no matter how many elements are next to it , Will not make this element unsatisfied , So the elements on both sides can be placed at will . The remaining middle , Because there are as many elements above and below , So the two elements on both sides of it must be larger than it at the same time or smaller than it at the same time .

Then you can try it at will .

Find out a a+2 a+1 a+4 a+3 a+6 a+5... This sequence is ok Of .

Then fill it in according to the rules .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define begin ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll n,t;
ll k;
void solve()
{
	cin>>n;
	if(n%2==1)
	{
		ll cnt=1;
		for(int i=1;i<=n;++i)
		{
			ll p=1+n*(i-1);
			if(i==1||i==n)
			{
				ll cnt=0;
				for(int j=1;j<=n;++j) cout<<p+(cnt++)<<' ';
				cout<<endl;
				continue;
			}
			cout<<p<<' ';
			ll cnt=1;
			for(int j=1;j<=(n-1)/2;++j)
			{
				cout<<p+(cnt)+1<<' '<<p+cnt<<' ';
				cnt+=2;
			}
			cout<<endl;
		}
		return;
	}
	else if(n%2==0)
	{
		ll cnt=1;
		for(int i=1;i<=n;++i)
		{
			ll p=1+n*(i-1);
			if(i==1||i==n)
			{
				ll cnt=0;
				for(int j=1;j<=n;++j) cout<<p+(cnt++)<<' ';
				cout<<endl;
				continue;
			}
			cout<<p<<' ';
			ll cnt=1;
			for(int j=1;j<=n/2-1;++j)
			{
				cout<<p+(cnt)+1<<' '<<p+cnt<<' ';
				cnt+=2;
			}
			cout<<p+cnt;
			cout<<endl;
		}
		return;
	}
	return;
}
int main()
{begin
	solve();
	return 0;
}

C - Tree Queries 

Carelessness ：

An interactive question （ Because the format of the question is not correct, it is useless to ask two questions ,shit...）

There is one n Tree of nodes . You can ask no more than n*2 A question , Each question can ask the distance between any two nodes （ Except for asking 1 ,2 Distance of ）.

And then let you ask 1,2 Distance of .

Ideas ：
Since you can ask so many questions , Based on the principle of "not for nothing" , Just connect all nodes to 1 and 2 Ask the distance , It just needs 2*n-4 A question .

Then there are two situations

1,2 The distance to 1：

See if there are any 1 The distance to 1 And to arrive 2 The distance to 2 The point of , If so, mark f1, If yes 2 The distance to 1 And to arrive 1 The distance to 2 The point of , Just mark f2.

If f1,f2 It's all marked , There are two situations ： 

Then just ask the distance between two points once , If not 1 Words , It can be explained that 1,2 The distance to 1 了 .

in addition , If f1,f2 Only one is marked , It can also show that 1,2 The distance to 1（ Self understanding ）

 

For most of the rest （1,2 distance ！=1）

Just for all to 1 The distance to 1 Find their points to 2 The minimum value of the distance between , Just add one .

So the whole is only 2*n-3 One inquiry will solve the problem .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define ser ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const ll N=110;
ll n;
ll dis[N];
ll p[N];
ll k;
void solve()
{
	std::cin>>n;
	memset(p,0x3f,sizeof p);
	memset(dis,0x3f,sizeof dis);
	//cout<<"HBK"<<endl;
	for(int i=3;i<=n;++i)
	{
		std::cout<<"? "<<i<<" "<<2<<endl;
		std::cin>>k;
		dis[i]=k;
	}
	for(int i=3;i<=n;++i)
	{
		std::cout<<"? "<<i<<" "<<1<<endl;
		std::cin>>k;
		p[i]=k;
	}
	ll f1=0,f2=0;
	for(int i=3;i<=n;++i){
		if(p[i]==1&&dis[i]==2) f1=i;
		if(p[i]==2&&dis[i]==1) f2=i;
	}
	if(f1&&f2)
	{
		std::cout<<"? "<<f1<<' '<<f2<<endl;
		//cout<<"sdddddd"<<endl;
		std::cin>>k;
		if(k==1);
		else
		{
			cout<<"! "<<1<<endl;
			return;
		}
	}
	if((f2&&!f1)||(f1&&!f2))
	{
		cout<<"! "<<1<<endl;
		return;
	}
	ll ans=10000;
	for(int i=3;i<=n;++i)
	{
		if(p[i]==1)
		{
			ans=min(ans,dis[i]);
		}
	}
	std::cout<<"! "<<ans+1;
}
int main()
{//ser
	solve();
	return 0;
}