oj.uz

Submission #312528

# Submission time Handle Problem Language Result Execution time Memory
312528 2020-10-13T16:24:12 Z mohamedsobhi777 Mouse (info1cup19_mouse) C++14
39.3333 / 100
 3000 ms 256 KB 
#include "grader.h"
#include<bits/stdc++.h>
using namespace std ; 
int n, num ;
vector<int> per, ans ; 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<int> indi ; 

void del(int x){
        for(int i = 0 ;i < (int) indi.size() ; ++ i){
                if(indi[i] == x){
                        indi.erase(indi.begin() + i , indi.begin() + i + 1) ; 
                        return ; 
                }
        }
}

void print(){
        for(int i = 0 ;i < n; ++ i)
                cout<< ans[i] <<" " ;
        cout<<".\n" ; 
}

void solve(int n){ 

        for(int i = 1;i <= n ; ++ i){
                ans.push_back(i) ; 
        }
        for(int i = 0 ;i < n; ++ i){
                indi.push_back(i) ; 
        }
        for(int i = 0 ;i < n; ++ i){
        //        int x ; cin >> x ;
        //        per.push_back(x) ; 
        }       

        random_shuffle(ans.begin() , ans.end() ) ; 
        int tim = 0 ; 
        int las = 0 ; 
        las = query(ans) ; 
        vector<int> goods ; 
        while(tim ++ < 1000000){
                int sz = (int) indi.size() ; 
                int x = rng() % sz ; 
                int y = rng() % sz ; 
                x = indi[x] ; 
                y = indi[y] ; 
                if(x == y)continue ; 
                swap(ans[x],ans[y]) ; 
                int now = query(ans) ; 
                if( abs(now - las) == 2){
                        del(x) ; del(y) ; 
                        goods.push_back(x) ; 
                        goods.push_back(y) ; 
                }else if(now == las + 1){
                        if(goods.size()){
                                int gud = goods.back() ; 
                                vector<int> qu = ans ;
                                swap(qu[gud],qu[x]) ; 
                                if(query(qu) == now - 2){
                                        del(x) ; 
                                }else{
                                        del(y) ; 
                                }
                        }
                }else if(now == las -1 && 0 ){
                        if(goods.size()){
                                int gud = goods.back() ; 
                                vector<int> qu = ans ;
                                swap(qu[x],qu[y]);
                                swap(qu[gud],qu[x]) ; 
                                if(query(qu) == now - 2){
                                        del(x) ; 
                                }else{
                                        del(y) ; 
                                }
                        }
                }

                if(now < las)swap(ans[x],ans[y]) ;
                las = max(las , now) ; 
                if(now == n)
                        break ;
        }
        return ; 
        if(las == n)
                cout<<"ok " ; 
        else {
                for(auto u : ans)cout<< u <<" " ; 
                        cout<<"incorrect " ; 
        }
        return ; 
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 30
2 Correct 1 ms 256 KB Correct! Number of queries: 3
3 Correct 0 ms 256 KB Correct! Number of queries: 10
4 Correct 1 ms 256 KB Correct! Number of queries: 9
5 Correct 1 ms 256 KB Correct! Number of queries: 14
6 Correct 0 ms 256 KB Correct! Number of queries: 17

Subtask #2
26.333316 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 30
2 Correct 1 ms 256 KB Correct! Number of queries: 3
3 Correct 0 ms 256 KB Correct! Number of queries: 10
4 Correct 1 ms 256 KB Correct! Number of queries: 9
5 Correct 1 ms 256 KB Correct! Number of queries: 14
6 Correct 0 ms 256 KB Correct! Number of queries: 17
7 Correct 11 ms 256 KB Correct! Number of queries: 800
8 Correct 14 ms 256 KB Correct! Number of queries: 800
9 Correct 8 ms 256 KB Correct! Number of queries: 700
10 Correct 13 ms 256 KB Correct! Number of queries: 800
11 Correct 6 ms 256 KB Correct! Number of queries: 500
12 Correct 14 ms 256 KB Correct! Number of queries: 700
13 Correct 9 ms 256 KB Correct! Number of queries: 700
14 Correct 12 ms 256 KB Correct! Number of queries: 800
15 Correct 12 ms 256 KB Correct! Number of queries: 900
16 Correct 14 ms 256 KB Correct! Number of queries: 900

Subtask #3
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Correct! Number of queries: 30
2 Correct 1 ms 256 KB Correct! Number of queries: 3
3 Correct 0 ms 256 KB Correct! Number of queries: 10
4 Correct 1 ms 256 KB Correct! Number of queries: 9
5 Correct 1 ms 256 KB Correct! Number of queries: 14
6 Correct 0 ms 256 KB Correct! Number of queries: 17
7 Correct 11 ms 256 KB Correct! Number of queries: 800
8 Correct 14 ms 256 KB Correct! Number of queries: 800
9 Correct 8 ms 256 KB Correct! Number of queries: 700
10 Correct 13 ms 256 KB Correct! Number of queries: 800
11 Correct 6 ms 256 KB Correct! Number of queries: 500
12 Correct 14 ms 256 KB Correct! Number of queries: 700
13 Correct 9 ms 256 KB Correct! Number of queries: 700
14 Correct 12 ms 256 KB Correct! Number of queries: 800
15 Correct 12 ms 256 KB Correct! Number of queries: 900
16 Correct 14 ms 256 KB Correct! Number of queries: 900
17 Execution timed out 3029 ms 256 KB Time limit exceeded
18 Halted 0 ms 0 KB -