Submission #1352456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1352456		Aviansh	Circuit 2 (JOI25_circuit2)	C++20	0 / 100	50 ms	1848 KiB

circuit2

#include <bits/stdc++.h>
#include "circuit.h"

using namespace std;
///get order
void dfs(int st, vector<int>g[], vector<int>&order){
    if(g[st].size()==0){
        order.push_back(st);
        return;
    }
    for(int i : g[st]){
        dfs(i,g,order);
    }
}

string solve(int n, int r, vector<int> u, vector<int> v) {
    vector<int>g[2*n+1];
    bool pleft[2*n+1];
    fill(pleft,pleft+2*n+1,0);
    int p[2*n+1];
    fill(p,p+2*n+1,-1);
    for(int i = 0;i<n;i++){
        swap(u[i],v[i]);
        g[i].push_back(u[i]);
        g[i].push_back(v[i]);
        pleft[v[i]]=1;
        p[v[i]]=i;
        p[u[i]]=i;
    }
    vector<int>order;
    dfs(0,g,order);
    set<int>ors;
    set<int>orind;
    int lo = n;
    int hi = 2*n;
    string fir = "";
    for(int i = 0;i<n;i++){
        fir+="0";
    }
    while(lo<hi){
        int lor = lo;
        int hir = hi;
        while(lor<hir){
            int mid = (lor+hir)/2;
            string quer = fir;
            for(int i = 0;i<=n;i++){
                quer+="0";
            }
            for(int i = 0;i<=mid-n;i++){
                if(orind.find(i)!=orind.end())
                    continue;
                quer[order[i]]='1';
            }
            bool x = query(quer);
            if(x){
                hir=mid;
            }
            else{
                lor=mid+1;
            }
        }
        orind.insert(lor);
        lo=lor+1;
        while(lor!=-1){
            if(pleft[lor]){
                lor=p[lor];
            }
            else{
                lor=p[lor];
                break;
            }
        }
        ors.insert(lor);
    }
    string ans = "";
    for(int i = 0;i<n;i++){
        if(ors.find(i)!=ors.end()){
            ans+="|";
        }
        else{
            ans+="&";
        }
    }
    return ans;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 1
• Subtask 3: 0 / 4
• Subtask 4: 0 / 5
• Subtask 5: 0 / 17
• Subtask 6: 0 / 8
• Subtask 7: 0 / 23
• Subtask 8: 0 / 8
• Subtask 9: 0 / 27
• Subtask 10: 0 / 7