oj.uz

답안 #843002

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843002 2023-09-03T14:30:52 Z coding_snorlax 가장 긴 여행 (IOI23_longesttrip) C++17
15 / 100
 597 ms 10064 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>10) {
   	//waste_time
    set<int> sjdfijdifdj;
    for(int k = 0;k<200000;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 0 ms 344 KB Output is correct
2 Correct 36 ms 9828 KB Output is correct

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 596 KB Output is correct
2 Correct 9 ms 344 KB Output is correct
3 Correct 559 ms 10064 KB Output is correct
4 Correct 236 ms 9800 KB Output is correct
5 Correct 130 ms 9800 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 583 ms 9800 KB Output is correct
4 Correct 229 ms 9816 KB Output is correct
5 Correct 137 ms 10064 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 9 ms 344 KB Output is correct
8 Correct 597 ms 9804 KB Output is correct
9 Correct 309 ms 9812 KB Output is correct
10 Correct 128 ms 9800 KB Output is correct
11 Correct 139 ms 9808 KB Output is correct
12 Correct 127 ms 9808 KB Output is correct
13 Correct 130 ms 9808 KB Output is correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 344 KB Output is correct
2 Correct 8 ms 344 KB Output is correct
3 Correct 580 ms 9556 KB Output is correct
4 Correct 223 ms 9816 KB Output is correct
5 Correct 134 ms 9816 KB Output is correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 9 ms 344 KB Output is correct
8 Correct 594 ms 9808 KB Output is correct
9 Correct 309 ms 9804 KB Output is correct
10 Correct 128 ms 9816 KB Output is correct
11 Correct 129 ms 9800 KB Output is correct
12 Correct 135 ms 10020 KB Output is correct
13 Correct 131 ms 9804 KB Output is correct
14 Correct 11 ms 344 KB Output is correct
15 Incorrect 2 ms 344 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 10 ms 344 KB Output is correct
3 Correct 573 ms 9816 KB Output is correct
4 Correct 220 ms 9804 KB Output is correct
5 Partially correct 133 ms 9816 KB Output is partially correct
6 Correct 7 ms 344 KB Output is correct
7 Correct 9 ms 496 KB Output is correct
8 Correct 582 ms 9800 KB Output is correct
9 Correct 288 ms 10060 KB Output is correct
10 Partially correct 127 ms 9808 KB Output is partially correct
11 Partially correct 129 ms 9808 KB Output is partially correct
12 Partially correct 132 ms 9816 KB Output is partially correct
13 Partially correct 126 ms 9816 KB Output is partially correct
14 Correct 14 ms 344 KB Output is correct
15 Incorrect 2 ms 344 KB Secret mismatch (possible tampering with the output).
16 Halted 0 ms 0 KB -