oj.uz

Submission #1110818

# Submission time Handle Problem Language Result Execution time Memory
1110818 2024-11-10T14:48:18 Z Pioneer Sphinx's Riddle (IOI24_sphinx) C++17
1.5 / 100
 6 ms 336 KB 
#include "sphinx.h"
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define sz(s) ((int)s.size())
#define all(v) v.begin(),v.end()

const int MAX=255;

struct dsu{
    int f[MAX];

    void init(int n){
        for(int i=0;i<n;i++)f[i]=i;
    }

    int get(int v){
        return (f[v]==v?v:f[v]=get(f[v]));
    }

    void unite(int a,int b){
        a=get(a),b=get(b);
        f[a]=b;
    }
}d,dd;

int n;
vector<int> g[MAX];

bool bar(int mid,int l,int r){
    vector<int> ask(n,-1);
    for(int i=0;i<mid;i++){
        if(d.get(i)<l||d.get(i)>r){
            ask[i]=n;
        }
    }
    for(int i=mid+1;i<n;i++)ask[i]=n;
    dd.init(n);
    for(int i=0;i<n;i++){
        for(auto to:g[i]){
            if(ask[i]==n&&ask[to]==n){
                dd.unite(i,to);
            }
        }
    }
    for(int i=0;i<mid;i++){
        for(auto to:g[i]){
            if(d.get(i)==d.get(to)){
                
                dd.unite(i,to);
            }
        }
    }
    vector<int> vec;
    for(int i=0;i<n;i++)vec.pb(dd.get(i));
    sort(all(vec));
    vec.erase(unique(all(vec)),vec.end());
    return (sz(vec)!=perform_experiment(ask));
}

vector<int> find_colours(int N,vector<int> X,vector<int> Y){
    n=N;
    for(int i=0;i<sz(X);i++){
        g[X[i]].pb(Y[i]);
        g[Y[i]].pb(X[i]);
    }
    d.init(n);
    for(int i=1;i<N;i++){
        vector<int> v;
        for(auto to:g[i]){
            if(to<i){
                v.pb(d.get(to));
            }
        }
        sort(all(v));
        v.erase(unique(all(v)),v.end());
        int l=0;
        vector<int> mrg;
        while(l<sz(v)&&bar(i,v[l],v.back())){
            int r=sz(v)-2,res=sz(v)-1;
            int L=l;
            while(L<=r){
                int mid=(L+r)/2;
                if(bar(i,v[l],v[mid])){
                    r=mid-1;
                    res=mid;
                }
                else{
                    L=mid+1;
                }
            }
            l=res+1;
            mrg.pb(res);
        }
        for(auto to:mrg){
            d.unite(i,to);
        }
    }
    vector<int> ans(n);
    for(int i=0;i<n;i++)ans[i]=d.get(i);
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct

Subtask #1
1.5 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 1 ms 336 KB Partially correct

Subtask #2
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Correct 1 ms 336 KB #experiments: 1
3 Correct 1 ms 336 KB #experiments: 1
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 2 ms 336 KB Partially correct
7 Incorrect 2 ms 336 KB Vertices 9 and 10 do have the same color, but they do not in returned answer
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 2 ms 336 KB Partially correct
6 Incorrect 2 ms 336 KB Vertices 9 and 10 do have the same color, but they do not in returned answer
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB #experiments: 1
2 Correct 1 ms 336 KB #experiments: 1
3 Partially correct 1 ms 336 KB Partially correct
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 3 ms 336 KB Partially correct
6 Incorrect 6 ms 336 KB Vertices 0 and 3 do not have the same color, but they do in returned answer
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 36.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 336 KB Partially correct
2 Correct 1 ms 336 KB #experiments: 1
3 Correct 1 ms 336 KB #experiments: 1
4 Partially correct 1 ms 336 KB Partially correct
5 Partially correct 1 ms 336 KB Partially correct
6 Partially correct 2 ms 336 KB Partially correct
7 Incorrect 2 ms 336 KB Vertices 9 and 10 do have the same color, but they do not in returned answer
8 Halted 0 ms 0 KB -