Submission #930748

#	Time	Username	Problem	Language	Result	Execution time	Memory
930748		abcvuitunggio	Mouse (info1cup19_mouse)	C++17	100 / 100	44 ms	1440 KiB

mouse

#include<bits/stdc++.h>
#include "grader.h"
using namespace std;
vector <int> v,found,ve[2];
int c[300],cnt;
set <pair <int, int>> s;
void add(int i){
    if (c[i])
        return;
    found.push_back(i);
    c[i]=1;
}
void shift(){
    int last=-1;
    for (int i=0;i<v.size();i++)
        if (!c[i]){
            if (last!=-1)
                swap(v[i],v[last]);
            last=i;
        }
}
int f(int l, int r, vector <int> not_found, int base, int need_to_check=1){
    if (need_to_check){
        for (int i=l;i<=r;i++)
            swap(v[not_found[i]],v[found[i-l]]);
        int x=query(v);
        for (int i=l;i<=r;i++)
            swap(v[not_found[i]],v[found[i-l]]);
        if (base-x==r-l+1)
            return r+1;
        s.insert({r,base-x-(r-l+1)});
    }
    int lo=l,hi=r-1,kq=r;
    while (lo<=hi){
        int mid=(lo+hi)>>1;
        for (int i=l;i<=mid;i++)
            swap(v[not_found[i]],v[found[i-l]]);
        int x=query(v);
        for (int i=l;i<=mid;i++)
            swap(v[not_found[i]],v[found[i-l]]);
        if (base-x>mid-l+1){
            s.insert({mid,base-x-(mid-l+1)});
            kq=mid;
            hi=mid-1;
        }
        else
            lo=mid+1;
    }
    cnt++;
    add(not_found[kq]);
    return kq+1;
}
void solve(int n) {
    v.assign(n,0);
    iota(v.begin(), v.end(), 1);
    int x=query(v),ch=0,ch2=0;
    if (x==n)
        return;
    for (int i=1;i<n;i++){
        swap(v[0],v[i]);
        int y=query(v);
        if (y==n)
            return;
        if (y-x==0)
            ch=1;
        else if (y-x==2){
            add(0),add(i);
            ch2=1;
            break;
        }
        else if (y-x==-2){
            swap(v[0],v[i]);
            add(0),add(i);
            ch2=1;
            break;
        }
        else
            ve[(y-x>0)].push_back(i);
        swap(v[0],v[i]);
    }
    if (!ch)
        add(0);
    else if (!ch2&&!ve[0].empty())
        for (int i:ve[0])
            add(i);
    else if (!ch2){
        assert(ve[1].size()==2);
        int a=ve[1][0],b=ve[1][1];
        swap(v[0],v[b]);
        swap(v[a],v[b]);
        int y=query(v);
        if (y==n)
            return;
        if (y-x<2)
            swap(v[0],v[b]);
        add(0);
    }
    while (1){
        int x=query(v);
        if (x==n)
            break;
        vector <int> not_found;
        for (int i=0;i<n;i++)
            if (!c[i])
                not_found.push_back(i);
        int i=0;
        cnt=0;
        s.clear();
        while (found.size()<x&&i<not_found.size()){
            while (!s.empty())
                if ((*s.begin()).second<=cnt)
                    s.erase(s.begin());
                else
                    break;
            if (s.empty()){
                int sz=min(found.size(),not_found.size()-i);
                i=f(i,i+sz-1,not_found,x);
            }
            else
                i=f(i,(*s.begin()).first,not_found,x,0);
        }
        shift();
    }
}

Compilation message (stderr)

mouse.cpp: In function 'void shift()':
mouse.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for (int i=0;i<v.size();i++)
      |                  ~^~~~~~~~~
mouse.cpp: In function 'void solve(int)':
mouse.cpp:109:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  109 |         while (found.size()<x&&i<not_found.size()){
      |                ~~~~~~~~~~~~^~
mouse.cpp:109:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         while (found.size()<x&&i<not_found.size()){
      |                                ~^~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 38 / 38
• Subtask 3: 49 / 49