oj.uz

Submission #937501

# Submission time Handle Problem Language Result Execution time Memory
937501 2024-03-04T07:20:00 Z guagua0407 Chameleon's Love (JOI20_chameleon) C++17
40 / 100
 33 ms 6228 KB 
#include "chameleon.h"
#include<bits/stdc++.h>

namespace {

using namespace std;
#define all(x) x.begin(),x.end()
map<vector<int>,int> mp;
int n;

int query(vector<int> vec){
    sort(vec.begin(),vec.end());
    if(mp.find(vec)!=mp.end()) return mp[vec];
    else{
        int x=Query(vec);
        mp[vec]=x;
        return x;
    }
}

void sir(vector<int> vec){
    sort(all(vec));
    if(mp.find(vec)==mp.end()){
        mp[vec]=-1;
    }
}

}  // namespace

void Solve(int N) {
    using namespace std;
    n=N;
    n*=2;
    /*vector<int> res(1<<n);
    for(int i=0;i<(1<<n);i++){
        vector<int> vec;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                vec.push_back(j+1);
            }
        }
        res[i]=Query(vec);
    }*/
    vector<vector<int>> one(n);
    vector<bool> two(n);

    for(int i=0;i<n;i++){
        for(int j=n-1;j>=0;j--){
            if(j==i) continue;
            if(query({i+1,j+1})==1) one[i].push_back(j);
            if((int)one[i].size()==3) break;
        }
        for(int j=0;j<n;j++){
            if(j==i) continue;
            sir({i,j});
        }
        if((int)one[i].size()==1) two[i]=true;
        else{
            int a=one[i][0];
            int b=one[i][1];
            int c=one[i][2];
            if(query({i+1,a+1,b+1})==1){
                one[i]={a,b};
                sir({i+1,b+1,c+1});
                sir({i+1,c+1,a+1});
            }
            else if(query({i+1,b+1,c+1})==1){
                one[i]={b,c};
                sir({i+1,a+1,b+1});
                sir({i+1,c+1,a+1});
            }
            else if(query({i+1,c+1,a+1})==1){
                one[i]={c,a};
                sir({i+1,a+1,b+1});
                sir({i+1,b+1,c+1});
            }
        }
    }
    vector<bool> used(n);
    for(int i=0;i<n;i++){
        if(used[i]) continue;
        if(two[i]){
            Answer(i+1,one[i][0]+1);
            used[i]=used[one[i][0]]=true;
            continue;
        }
        int a=one[i][0];
        int b=one[i][1];
        if(two[a]){
            Answer(i+1,a+1);
            used[i]=used[a]=true;
            continue;
        }
        else if(two[b]){
            Answer(i+1,b+1);
            used[i]=used[b]=true;
            continue;
        }
        else{
            if(one[a][0]==i or one[a][1]==i){
                Answer(i+1,a+1);
                used[i]=used[a]=true;
            }
            else{
                Answer(i+1,b+1);
                used[i]=used[b]=true;
            }
        }
    }
    /*return ;
    for(int i=0;i<(1<<n);i++){
        vector<int> same(n);
        vector<int> prv(n,-1);
        for(int j=0;j<n;j++){
            if(two[j]) continue;
            if(i&(1<<j)){
                same[j]=1;
                prv[one[j][0]]=j;
            }
            else{
                same[j]=0;
                prv[one[j][1]]=j;
            }
        }
        bool tf=true;
        for(int j=0;j<n;j++){
            if(two[j]) continue;
            int x=prv[j];
            if(x==-1){
                tf=false;
                break;
            }
            int y=one[j][same[j]];
            if(y==-1){
                tf=false;
                break;
            }
            int ans=res[(1<<x)|(1<<j)|(1<<y)];
            if(ans!=1){
                tf=false;
                break;
            }
        }
        if(tf){
            vector<bool> used(n);
            for(int j=0;j<n;j++){
                if(used[j]) continue;
                int x=one[j][same[j]];
                assert(!used[x]);
                Answer(j+1,x+1);
                used[j]=used[x]=true;
            }
        }
    }*/
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 22 ms 2764 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 4 ms 856 KB Output is correct
11 Correct 4 ms 856 KB Output is correct
12 Correct 4 ms 856 KB Output is correct
13 Correct 4 ms 856 KB Output is correct
14 Correct 4 ms 856 KB Output is correct
15 Correct 5 ms 856 KB Output is correct
16 Correct 4 ms 856 KB Output is correct
17 Correct 4 ms 856 KB Output is correct
18 Correct 4 ms 856 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 33 ms 6228 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 22 ms 2764 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -