oj.uz

답안 #843008

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843008 2023-09-03T14:35:05 Z coding_snorlax 가장 긴 여행 (IOI23_longesttrip) C++17
15 / 100
 539 ms 2908 KB 
#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
set<int> un_process;
vector<int> B_complex_graph(vector<int> A,vector<int> B){
    set<int> test;
    vector<int> test_1;
    for(int i:A){
        if(test.find(i)!=test.end()) return test_1;
        test.insert(i);
    }
    for(int i:B){
        if(test.find(i)!=test.end()) return test_1;
        test.insert(i);
    }
    // B is a complex_graph set
    vector<int> tmp={0},tmp1={0};
    tmp[0] = A[0];
    if(!are_connected(tmp,B)){
        // now A[0],A.back() connected
        // only need to find one edge between A and B or return no such edge
        int L = 0;int R = (int) B.size()-1;int M = (L+R)/2;
        while(L!=R){
            vector<int> query;
            M = (L+R)/2;
            for(int i=L;i<=M;i++){
                query.push_back(B[i]);
            }
            if(!are_connected(A,query)) L = M+1;
            else R = M;
        }
        int l = 0;int r = (int) A.size()-1;int m = (L+R)/2;
        while(l!=r){
            vector<int> query;
            m = (l+r)/2;
            for(int i=l;i<=m;i++){
                query.push_back(A[i]);
            }
            tmp[0]=B[L];
            if(!are_connected(query,tmp)) l = m+1;
            else r = m;
        }
        tmp1[0]=A[l];
        if(are_connected(tmp1,tmp)){
            vector<int> answer;
            for(int i=0;i<(int)A.size();i++) answer.push_back(A[(i+l+1)%((int)A.size())]);
            answer.push_back(B[L]);
            for(int i=0;i<(int)B.size()-1;i++) answer.push_back(B[(i+L+1)%((int)B.size())]);
            return answer;
        }
        else{
            return A;
        }
    }
    else{
        int L = 0;int R = (int) B.size()-1;int M = (L+R)/2;
        while(L!=R){
            vector<int> query;
            M = (L+R)/2;
            for(int i=L;i<=M;i++){
                query.push_back(B[i]);
            }
            if(!are_connected(tmp,query)) L = M+1;
            else R = M;
        }
        vector<int> answer;
        for(int i=(int)A.size()-1;i>=0;i--) answer.push_back(A[i]);
        answer.push_back(B[R]);
        //cout << "B_size" << (int)B.size() << "\n";
        for(int i=0;i<(int)B.size()-1;i++) answer.push_back(B[(i+R+1)%((int)B.size())]);
        return answer;
    }
}
vector<int> Process(vector<int> C,vector<int> D){
    if((int)D.size()==0) {return C;}
    vector<int> A,B;
    if((int)C.size()<(int)D.size()){A=D;B=C;}
    else{A=C;B=D;}
    vector<int> tmp = {1};
    tmp[0] = A.back();
    if(!are_connected(tmp,B)){
        return B_complex_graph(A,B);
    }
    else{
        int L = 0;int R = (int) B.size()-1;int M = (L+R)/2;
        while(L!=R){
            vector<int> query;
            M = (L+R)/2;
            cout << M << " \n";
            for(int i=L;i<=M;i++){
                query.push_back(B[i]);
            }
            if(!are_connected(tmp,query)) L = M+1;
            else R = M;
        }
        vector<int> new_B;
        if(L > (int)B.size()/2){
            for(int i=L;i>=0;i--){
                A.push_back(B[i]);
            }
            for(int i=L+1;i<(int)B.size();i++){
                new_B.push_back(B[i]);
            }
        }
        else{
            for(int i=L;i<(int)B.size();i++){
                A.push_back(B[i]);
            }
            for(int i=L-1;i>=0;i--){
                new_B.push_back(B[i]);
            }
        }
        return Process(A,new_B);
    }
}
vector<int> longest_trip(int N, int D)
{
    if(N>4) {
   	//waste_time
    set<int> sjdfijdifdj;
    for(int k = 0;k<50000;k++){
      sjdfijdifdj.insert(k);
    }
    }
    un_process.clear();
    for(int i=2;i<N;i++){
        un_process.insert(i);
    }
    vector<int> a={0};
    vector<int> b={1};
    while((int)un_process.size()>=1){
        vector<int> ask1 = {a.back()};
        vector<int> ask2 = {b.back(),*un_process.begin()};
        if(are_connected(ask1,ask2)){
            vector<int> ask3 = {a.back()};
            vector<int> ask4 = {*un_process.begin()};
            if(are_connected(ask3,ask4)) a.push_back(*un_process.begin());
            else{
                for(int i = (int)b.size()-1;i>=0;i--) a.push_back(b[i]);
                b.clear();
                b.push_back(*un_process.begin());
            }
        }
        else{
            b.push_back(*un_process.begin());
        }
        un_process.erase(un_process.begin());
    }
    return Process(a,b);
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 2648 KB Output is correct
2 Correct 9 ms 2648 KB Output is correct

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 532 ms 2648 KB Output is correct
3 Correct 124 ms 2648 KB Output is correct
4 Correct 53 ms 2904 KB Output is correct
5 Correct 37 ms 2772 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 344 KB Output is correct
2 Correct 535 ms 2668 KB Output is correct
3 Correct 133 ms 2648 KB Output is correct
4 Correct 53 ms 2780 KB Output is correct
5 Correct 35 ms 2776 KB Output is correct
6 Correct 6 ms 344 KB Output is correct
7 Correct 539 ms 2648 KB Output is correct
8 Correct 123 ms 2904 KB Output is correct
9 Correct 73 ms 2780 KB Output is correct
10 Correct 36 ms 2780 KB Output is correct
11 Correct 36 ms 2904 KB Output is correct
12 Correct 34 ms 2904 KB Output is correct
13 Correct 34 ms 2904 KB Output is correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 529 ms 2648 KB Output is correct
3 Correct 128 ms 2904 KB Output is correct
4 Correct 54 ms 2904 KB Output is correct
5 Correct 35 ms 2908 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 535 ms 2648 KB Output is correct
8 Correct 125 ms 2904 KB Output is correct
9 Correct 68 ms 2648 KB Output is correct
10 Correct 33 ms 2904 KB Output is correct
11 Correct 37 ms 2784 KB Output is correct
12 Correct 35 ms 2780 KB Output is correct
13 Correct 37 ms 2904 KB Output is correct
14 Correct 13 ms 344 KB Output is correct
15 Incorrect 160 ms 2648 KB Secret mismatch (possible tampering with the output).
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 534 ms 2648 KB Output is correct
3 Correct 124 ms 2648 KB Output is correct
4 Correct 56 ms 2904 KB Output is correct
5 Partially correct 36 ms 2904 KB Output is partially correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 527 ms 2648 KB Output is correct
8 Correct 124 ms 2648 KB Output is correct
9 Correct 68 ms 2648 KB Output is correct
10 Partially correct 34 ms 2904 KB Output is partially correct
11 Partially correct 36 ms 2780 KB Output is partially correct
12 Partially correct 40 ms 2868 KB Output is partially correct
13 Partially correct 35 ms 2904 KB Output is partially correct
14 Correct 10 ms 344 KB Output is correct
15 Incorrect 171 ms 2536 KB Secret mismatch (possible tampering with the output).
16 Halted 0 ms 0 KB -