Submission #1018858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018858		Unforgettablepl	Flights (JOI22_flights)	C++17	15 / 100	4000 ms	2492 KiB

Ali

#pragma GCC optimize("Ofast","unroll-loops")
#include "Ali.h"
#include <bits/stdc++.h>
using namespace std;

const int CASES = 48;

namespace {

vector<vector<int>> adj;
int n;

}

void Init(int N, vector<int> U, vector<int> V) {
    adj = vector<vector<int>>(N);
    n = N;
    for(int i=0;i<n-1;i++){
        adj[U[i]].emplace_back(V[i]);
        adj[V[i]].emplace_back(U[i]);
    }
    for(int i=0;i<N;i++)SetID(i,i);
}

string SendA(string S) {
    assert(S.size()==20);
    int x = 0;
    for(int bit=0;bit<20;bit++)if(S[bit]=='1')x|=(1<<bit);
    int curr = 0;
    int num = 0;
    vector<pair<int,int>> possibilities;
    for(int l=0;l<n;l++){
        for(int r=l+1;r<n;r++){
            if(num==CASES){
                num = 0;
                curr++;
            }
            num++;
            if(curr==x)possibilities.emplace_back(l,r);
        }
    }
    int tar = -1;
    function<int(int,int)> dfs = [&](int x,int p){
        if(tar==x)return 0;
        int ans = 1e5;
        for(int&i:adj[x])if(i!=p)ans=min(ans,dfs(i,x)+1);
        return ans;
    };
    string res;
    for(auto[a,b]:possibilities){
        tar = b;
        int ans = dfs(a,-1);
        for(int bit=0;bit<14;bit++){
            if(ans&(1<<bit))res.insert(res.end(),'1');
            else res.insert(res.end(),'0');
        }
    }
    return res;
}

Benjamin

#pragma GCC optimize("Ofast","unroll-loops")
#include "Benjamin.h"
#include <bits/stdc++.h>
using namespace std;

const int CASES = 48;

namespace {

int possno;

}

string SendB(int N, int X, int Y) {
    int curr = 0;
    int num = 0;
    int mine = 0;
    if(Y<X)swap(X,Y);
    vector<pair<int,int>> possibilities;
    for(int l=0;l<N;l++){
        for(int r=l+1;r<N;r++){
            if(num==CASES){
                num = 0;
                curr++;
            }
            num++;
            if(l==X and r==Y)mine=curr;
        }
    }
    string res;
    for(int bit=0;bit<20;bit++){
        if(mine&(1<<bit))res.insert(res.end(),'1');
        else res.insert(res.end(),'0');
    }
    curr = 0;
    num = 0;
    for(int l=0;l<N;l++){
        for(int r=l+1;r<N;r++){
            if(num==CASES){
                num = 0;
                curr++;
            }
            num++;
            if(curr==mine)possibilities.emplace_back(l,r);
        }
    }
    for(int i=0;i<possibilities.size();i++){
        if(possibilities[i]==make_pair(X,Y))possno=i;
    }
    assert(res.size()==20);
    return res;
}

int Answer(string T) {
    assert(T.size()>=14);
    int ans = 0;
    for(int bit=0;bit<14;bit++)if(T[possno*14 + bit]=='1')ans|=(1<<bit);
    return ans;
}

Compilation message (stderr)

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In function 'std::string SendB(int, int, int)':
Benjamin.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<possibilities.size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 85