oj.uz

Submission #930748

# Submission time Handle Problem Language Result Execution time Memory
930748 2024-02-20T11:13:42 Z abcvuitunggio Mouse (info1cup19_mouse) C++17
100 / 100
 44 ms 1440 KB 
#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

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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 16
2 Correct 0 ms 344 KB Correct! Number of queries: 8
3 Correct 0 ms 596 KB Correct! Number of queries: 14
4 Correct 0 ms 344 KB Correct! Number of queries: 19
5 Correct 0 ms 344 KB Correct! Number of queries: 17
6 Correct 0 ms 344 KB Correct! Number of queries: 11

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 16
2 Correct 0 ms 344 KB Correct! Number of queries: 8
3 Correct 0 ms 596 KB Correct! Number of queries: 14
4 Correct 0 ms 344 KB Correct! Number of queries: 19
5 Correct 0 ms 344 KB Correct! Number of queries: 17
6 Correct 0 ms 344 KB Correct! Number of queries: 11
7 Correct 2 ms 436 KB Correct! Number of queries: 300
8 Correct 2 ms 436 KB Correct! Number of queries: 300
9 Correct 2 ms 432 KB Correct! Number of queries: 300
10 Correct 2 ms 432 KB Correct! Number of queries: 300
11 Correct 1 ms 440 KB Correct! Number of queries: 300
12 Correct 2 ms 440 KB Correct! Number of queries: 300
13 Correct 2 ms 440 KB Correct! Number of queries: 300
14 Correct 2 ms 440 KB Correct! Number of queries: 300
15 Correct 3 ms 436 KB Correct! Number of queries: 300
16 Correct 2 ms 440 KB Correct! Number of queries: 300

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Correct! Number of queries: 16
2 Correct 0 ms 344 KB Correct! Number of queries: 8
3 Correct 0 ms 596 KB Correct! Number of queries: 14
4 Correct 0 ms 344 KB Correct! Number of queries: 19
5 Correct 0 ms 344 KB Correct! Number of queries: 17
6 Correct 0 ms 344 KB Correct! Number of queries: 11
7 Correct 2 ms 436 KB Correct! Number of queries: 300
8 Correct 2 ms 436 KB Correct! Number of queries: 300
9 Correct 2 ms 432 KB Correct! Number of queries: 300
10 Correct 2 ms 432 KB Correct! Number of queries: 300
11 Correct 1 ms 440 KB Correct! Number of queries: 300
12 Correct 2 ms 440 KB Correct! Number of queries: 300
13 Correct 2 ms 440 KB Correct! Number of queries: 300
14 Correct 2 ms 440 KB Correct! Number of queries: 300
15 Correct 3 ms 436 KB Correct! Number of queries: 300
16 Correct 2 ms 440 KB Correct! Number of queries: 300
17 Correct 40 ms 696 KB Correct! Number of queries: 2100
18 Correct 38 ms 692 KB Correct! Number of queries: 2000
19 Correct 36 ms 1196 KB Correct! Number of queries: 2200
20 Correct 37 ms 960 KB Correct! Number of queries: 2000
21 Correct 41 ms 932 KB Correct! Number of queries: 2300
22 Correct 35 ms 948 KB Correct! Number of queries: 2100
23 Correct 38 ms 704 KB Correct! Number of queries: 2100
24 Correct 38 ms 1440 KB Correct! Number of queries: 2100
25 Correct 38 ms 1216 KB Correct! Number of queries: 2100
26 Correct 44 ms 696 KB Correct! Number of queries: 2200