oj.uz

Submission #705054

# Submission time Handle Problem Language Result Execution time Memory
705054 2023-03-03T10:02:54 Z MtSaka Monster Game (JOI21_monster) C++17
0 / 100
 82 ms 800 KB 
#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;i--)
#define all(x) begin(x),end(x)
using ll=long long;
using namespace std;
using ull=unsigned long long;
template<typename T,typename U>
inline bool chmax(T&a,const U&b){return (a<b)?a=b,true:false;}
template<typename T,typename U>
inline bool chmin(T&a,const U&b){return (a>b)?a=b,true:false;}
#include "monster.h"
map<pair<int,int>,bool>mp;
bool ask(int a,int b){
  if(mp.count({a,b}))return mp[{a,b}];
  if(mp.count({b,a}))return !mp[{b,a}];
  return mp[{a,b}]=Query(a,b);
}
void merge(vector<int>&v){
  if(v.size()==1)return;
  int mid=v.size()/2;
  vector<int>l(v.begin(),v.begin()+mid),r(v.begin()+mid,v.end());
  merge(l),merge(r);
  int i=0,j=0;
  rep(k,0,v.size()){
    if(i==l.size())v[k]=r[j++];
    else if(j==r.size())v[k]=l[i++];
    else if(ask(l[i],r[j]))v[k]=r[j++];
    else v[k]=l[i++];
  }
  return;
}
int sol2(const vector<int>&id){
  int n=id.size();
  vector<int>cnt(n,0);
  vector<vector<int>>a(n,vector<int>(n,0));
  rep(i,0,n)rep(j,i+1,n){
    bool f=ask(id[i],id[j]);
    if(f)cnt[i]++;
    else cnt[j]++;
    a[i][j]=f;
    a[j][i]=!f;
  }
  rep(i,0,n){
    if(cnt[i]==0)return i;
    if(cnt[i]==1){
      rep(j,0,n)if(cnt[j]==1){
        if(a[i][j])return i;
        return j;
      }
    }
  }
  return -1;
}
vector<int>Solve(int n){
  vector<int>id(n);
  iota(id.begin(),id.end(),0);
  merge(id);
  vector<int>tmp(id.begin(),id.begin()+min(10,n));
  int mi=sol2(tmp);
  int start=id[mi];
  id.erase(id.begin()+mi);
  id.insert(id.begin(),start);
  rep(i,1,n){
    int j=i;
    while(j<n&&ask(id[j],start))j++;
    reverse(id.begin()+i,id.begin()+min(j+1,n));
    if(j==n)break;
    start=id[j];
    i=j;
  }
  vector<int>ret(n);
  rep(i,0,n)ret[id[i]]=i;
  return ret;
}

Compilation message

monster.cpp: In function 'void merge(std::vector<int>&)':
monster.cpp:26:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     if(i==l.size())v[k]=r[j++];
      |        ~^~~~~~~~~~
monster.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     else if(j==r.size())v[k]=l[i++];
      |             ~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Incorrect 0 ms 208 KB Wrong Answer [3]
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Incorrect 0 ms 208 KB Wrong Answer [3]
6 Halted 0 ms 0 KB -

Subtask #3
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 800 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -