oj.uz

Submission #101234

# Submission time Handle Problem Language Result Execution time Memory
101234 2019-03-18T02:47:43 Z ShaneOng ICC (CEOI16_icc) C++14
0 / 100
 15 ms 896 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> ii;
vector<int> col,adj[109];
void dfs(int u){
    for(int v:adj[u]){
        if(col[v]==-1){
            col[v]=1-col[u];
            dfs(v);
        }
    }
}
ii stuff(vector<int> a,vector<int> b){
    int qu=query(a.size(),b.size(),&a[0],&b[0]);
    /*printf("\na:");
    for(int x:a)
        printf("%d ",x);
    printf("\n");
    printf("b:");
    for(int x:b)
        printf("%d ",x);
    printf("\n");*/
    int na=(int)a.size(),nb=(int)b.size();
    ii res=ii(-1,-1);
    if(qu==0){
        vector<int> aa,ab,ba,bb;
        if(na>1){
            for(int x=0;x<na;x++){
                if(x<na/2)
                    aa.push_back(a[x]);
                else
                    ab.push_back(a[x]);
            }
            res=max(res,stuff(aa,ab));
        }
        if(nb>1){
            for(int x=0;x<nb;x++){
                if(x<nb/2)
                    ba.push_back(b[x]);
                else
                    bb.push_back(b[x]);
            }
            res=max(res,stuff(ba,bb));
        }

        return res;
    }else{
        while((int)a.size()>1){
            vector<int> a1,a2;
            for(int x=0;x<(int)a.size();x++){
                if(x<(int)a.size()/2)
                    a1.push_back(a[x]);
                else
                    a2.push_back(a[x]);
            }
            int qu=query(a1.size(),b.size(),&a1[0],&b[0]);
            if(qu==0){
                a=a2;
            }else
                a=a1;
        }
        while((int)b.size()>1){
            vector<int> b1,b2;
            for(int x=0;x<(int)b.size();x++){
                if(x<(int)b.size()/2)
                    b1.push_back(b[x]);
                else
                    b2.push_back(b[x]);
            }
            int qu=query(a.size(),b1.size(),&a[0],&b1[0]);
            if(qu==0){
                b=b2;
            }else
                b=b1;
        }
        //printf("%d %d\n",a[0],b[0]);
        return ii(a[0],b[0]);

    }
}
void run(int n) {
    for(int x=0;x<n-1;x++){
        col.assign(n,-1);
        vector<int> arr[4];
        for(int y=0;y<n;y++){
            if(col[y]==-1){
                col[y]=y%2;
                arr[y%2].push_back(y+1);
                dfs(y);
            }else{
                arr[col[y]+2].push_back(y+1);
            }
        }
        ii ans=max(stuff(arr[0],arr[2]),stuff(arr[1],arr[3]));
        adj[ans.first-1].push_back(ans.second-1);
        adj[ans.second-1].push_back(ans.first-1);
        //printf("%d %d\n",ans.first,ans.second);
        setRoad(ans.first,ans.second);
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -