Submission #711252

#	Time	Username	Problem	Language	Result	Execution time	Memory
711252		Antekb	Monster Game (JOI21_monster)	C++17	0 / 100	142 ms	2352 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;
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;
    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;
    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){
    			bool b=czy(l.back()[0], r.back()[0]);
    			if(b!=czy(l.back()[1], r.back()[0])){
    				b=czy(l.back()[2], r.back()[0]);
    			}
    			if(b)res.pb(l.back()), l.pp();
    			else res.pb(r.back()), r.pp();
    		}
    		else if(r.back().size()==3){
    			bool b=czy(r.back()[0], l.back()[0]);
    			if(b!=czy(r.back()[1], l.back()[0])){
    				b=czy(r.back()[2], l.back()[0]);
    			}
    			if(b)res.pb(r.back()), r.pp();
    			else res.pb(l.back()), l.pp();
    		}
    		else{
    			if(czy(l.back()[0], r.back()[0])){
    				if(r.size()>=2 && czy(r[r.size()-2][0], l.back()[0])){
    					vi V2;
    					V2.pb(l.back()[0]);
    					l.pp();
    					V2.pb(r.back()[0]);
    					r.pp();
    					V2.pb(r.back()[0]);
    					r.pp();
    					l.pb(V2);
    				}
    				else{
    					res.pb(l.back());
    					l.pp();
    				}
    			}
    			else{
    				if(l.size()>=2 && czy(l[l.size()-2][0], r.back()[0])){
    					vi V2;
    					V2.pb(l.back()[0]);
    					l.pp();
    					V2.pb(r.back()[0]);
    					r.pp();
    					V2.pb(l.back()[0]);
    					l.pp();
    					l.pb(V2);
    				}
    				else{
    					res.pb(r.back());
    					r.pp();
    				}
    			}
    		}
    	}
    }
    reverse(all(res));
    //deb(V);
   // 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;
    for(int i=0; i<V.size(); i++){
    	if(V[i].size()==3)lst=i;
    	if(lst==i-2){
    		swap(V[i], V[i-1]);
    		lst=i;
    	}
    }
    //deb(V);
    for(int i=1; i<n; i++){
    	bool b=0;
    	for(int &j:V[i-1]){
    		for(int &k:V[i]){
    			if(!czy(k, j)){
    				//deb(k, j);
    				swap(V[i-1].back(), j);
    				swap(V[i][0], k);
    //deb(V);
    				b=1;
    			}
    			if(b)break;
    		}
    		if(b)break;
    	}
    }
    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:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0; i<V.size(); i++){
      |                  ~^~~~~~~~~
monster.cpp: In function 'vi Solve(int)':
monster.cpp:124:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for(int i=0; i<V.size(); i++){
      |                  ~^~~~~~~~~

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