Submission #711305

#	Time	Username	Problem	Language	Result	Execution time	Memory
711305		Antekb	Monster Game (JOI21_monster)	C++17	75 / 100	164 ms	1424 KiB

monster

#include<bits/stdc++.h>

#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pp pop_back
#define all(x) (x).begin(), (x).end()

using namespace std;

void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){
  cerr<<h;
  if(sizeof...(t)){cerr<<", ";debug(t...);}
}
template<typename T>
void debug(vector<T> V){
	cerr<<"{";
	for(int i=0; i<V.size(); i++){
		debug(V[i]);
		if(i+1!=V.size())cerr<<", ";
	}
	cerr<<"}";
}
#define deb(x...) cerr<<#x<<" = ";debug(x);cerr<<"\n";

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;
using vvi = vector<vi>;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#include "monster.h"
map<pii, bool> M;
map<int, int> S[2];
bool czy(int a, int b){//T[a]>T[b]
    int ans=0;
    if(a>b)ans^=1, swap(a, b);
    if(M.find(mp(a, b))==M.end()){
        M[{a, b}]=Query(a, b);
    }
    return ans^M[{a, b}];
}
vvi solve(vi V){
    if(V.size()==1)return {{V[0]}};
    vi L, R;
    shuffle(all(V), rng);
    for(int i=0; i<V.size(); i++){
        if(i&1)L.pb(V[i]);
        else R.pb(V[i]);
    }
    vvi l=solve(L);
    vvi r=solve(R);
    vvi res;
    //deb(V);
    while(l.size() || r.size()){
    	if(!r.size())res.pb(l.back()), l.pp();
    	else if(!l.size())res.pb(r.back()), r.pp();
    	else{
    		if(l.back().size()==3){
    			//deb("a");
    			bool b=czy(l.back()[0], r.back()[0]);
    			if(S[b^1].find(l.back()[0])!=S[b^1].end()){
    				if(S[b^1][l.back()[0]]==r.back()[0])b^=1;
    			}
    			else if(b!=czy(l.back()[1], r.back()[0])){
    				b=czy(l.back()[2], r.back()[0]);
    				//deb(l.back()[0], b);
    				S[b][l.back()[0]]=r.back()[0];
    				S[b][l.back()[1]]=r.back()[0];
    				S[b][l.back()[2]]=r.back()[0];
    			}
    			//deb(b);
    			if(b)res.pb(l.back()), l.pp();
    			else{
    				//deb("aa");
    				if(r.back().size()==1 && res.size()>=2 && res.back().size()==1 && res[res.size()-2].size()==1){
    					if(!czy(res[res.size()-2][0], r.back()[0])){
    						r.back().pb(res[res.size()-2][0]);
    						r.back().pb(res.back()[0]);
    						res.pp();
    						res.pp();
    					}
    				}
    				res.pb(r.back()), r.pp();
    			}
    		}
    		else if(r.back().size()==3){
    			//deb("b");
    			//deb(l);
    			//deb(r);
    			//deb(res);
    			bool b=czy(r.back()[0], l.back()[0]);
    			if(S[b^1].find(l.back()[0])!=S[b^1].end()){
    				if(S[b^1][l.back()[0]]==r.back()[0])b^=1;
    			}
    			else if(b!=czy(r.back()[1], l.back()[0])){
    				b=czy(r.back()[2], l.back()[0]);
    				//deb(r.back()[0], b);
    				S[b][r.back()[0]]=l.back()[0];
    				S[b][r.back()[1]]=l.back()[0];
    				S[b][r.back()[2]]=l.back()[0];
    			}
    			if(b)res.pb(r.back()), r.pp();
    			else{
    				//deb("bb");
    				if(res.size()>=2 && res.back().size()==1 && res[res.size()-2].size()==1){
    					if(!czy(res[res.size()-2][0], l.back()[0])){
    						l.back().pb(res[res.size()-2][0]);
    						l.back().pb(res.back()[0]);
    						res.pp();
    						res.pp();
    					}
    				}
    				res.pb(l.back()), l.pp();
    			}
    		}
    		else{
    			if(czy(l.back()[0], r.back()[0])){
    				//deb("c");
    				if(r.size()>=2 && r[r.size()-2].size()==1 && czy(r[r.size()-2][0], l.back()[0])){
    					//deb("cc");
    					vi V2;
    					V2.pb(l.back()[0]);
    					l.pp();
    					V2.pb(r.back()[0]);
    					r.pp();
    					V2.pb(r.back()[0]);
    					r.pp();
    					r.pb(V2);
    					//deb(l);
    					//deb(r);
    				}
    				else{
    					res.pb(l.back());
    					l.pp();
    				}
    			}
    			else{
    				//deb("d");
    				if(l.size()>=2 && l[l.size()-2].size()==1 && czy(l[l.size()-2][0], r.back()[0])){
    					vi V2;
    					V2.pb(r.back()[0]);
    					r.pp();
    					V2.pb(l.back()[0]);
    					l.pp();
    					V2.pb(l.back()[0]);
    					l.pp();
    					l.pb(V2);
    					//deb(l);
    					//deb(r);
    				}
    				else{
    					res.pb(r.back());
    					r.pp();
    				}
    			}
    		}
    	}
    	//deb(res);
    }
    reverse(all(res));
   	//deb(res);
    return res;
}

vi Solve(int n) {
    vi VV;
    for(int i=0; i<n; i++)VV.pb(i);
    vvi V=solve(VV);
    int lst=-1;
    //deb(V);
    for(int i=0; i<V.size(); i++){
    	if(V[i].size()==3)lst=i;
    	if(lst==i-2 && czy(V[i][0], V[i-1][0])){
    		swap(V[i], V[i-1]);
    		lst=i;
    	}
    }
    //deb(V);
    deb(M.size());
    for(int i=1; i<V.size(); i++){
    	//deb(i+1);
    	bool b=0;
    	for(int j=V[i-1].size()-1; j>=0; j--){
    		for(int k=0; k<V[i].size(); k++){
    			//deb(i);
    			if(!czy(V[i][k], V[i-1][j])){
    				//deb(k, j, i);
    				while(j!=V[i-1].size()-1){
    					swap(V[i-1][2], V[i-1][1]);
    					swap(V[i-1][1], V[i-1][0]);
    					j++;
    				}
    				while(k!=0 && k!=3){
    					swap(V[i][2], V[i][1]);
    					swap(V[i][1], V[i][0]);
    					k++;
    				}
    				//deb(V);
    				//deb(k, j, i);
    				b=1;
    			}
    			if(b)break;
    		}
    		if(b)break;
    	}
    }
    deb(M.size());
   	//deb(V);
    vi res(n);
    int wsk=0;
    for(vi v:V){
    	for(int i:v){
    		res[i]=wsk++;
    	}
    }
    return res;
}

Compilation message (stderr)

monster.cpp: In function 'vvi solve(vi)':
monster.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i=0; i<V.size(); i++){
      |                  ~^~~~~~~~~
monster.cpp: In function 'vi Solve(int)':
monster.cpp:177:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for(int i=0; i<V.size(); i++){
      |                  ~^~~~~~~~~
monster.cpp:186:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |     for(int i=1; i<V.size(); i++){
      |                  ~^~~~~~~~~
monster.cpp:190:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |       for(int k=0; k<V[i].size(); k++){
      |                    ~^~~~~~~~~~~~
monster.cpp:194:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |         while(j!=V[i-1].size()-1){
      |               ~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 50 / 75