Submission #1103325

#TimeUsernameProblemLanguageResultExecution timeMemory
1103325raduvMouse (info1cup19_mouse)C++17
83.23 / 100
324 ms3408 KiB
#include <bits/stdc++.h> //#define DEBUG //#define PRINTQ #ifndef DEBUG #include "grader.h" #endif // DEBUG using namespace std; #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> const int MAXN = 256; ordered_set candidates[MAXN + 1]; ordered_set available, cavailable; bool isset[MAXN + 1]; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); static inline long long genrand() { int x = abs(uniform_int_distribution<long long>(0, (long long)-1)(rng) * 3231311253412327863) % 1219083123232943211; return x; } #ifdef DEBUG int p[MAXN + 1] = {43, 49, 22, 11, 29, 50, 26, 44, 4, 38, 48, 21, 7, 13, 24, 47, 41, 6, 9, 12, 25, 42, 18, 17, 1, 39, 27, 28, 46, 36, 14, 5, 3, 20, 31, 37, 30, 45, 16, 15 ,32, 35, 8, 10, 33, 34, 2, 19, 40, 23}; int n = 50; int nq = 0; int st1 = 1; std::vector<int> ans; #endif // DEBUG #ifdef DEBUG int isPermutation(std::vector<int> q){ std::sort(q.begin(), q.end()); int i = 1; for(auto x : q){ if(x != i) return 0; i++; } return 1; } #endif // DEBUG #ifdef DEBUG int query(std::vector<int> q){ #ifdef PRINTQ for(auto x : q) printf("%d ", x); printf(" perm : %d", isPermutation(q)); printf("\n"); #endif // PRINTQ nq++; st1 = std::min(st1, (int)isPermutation(q)); int x = 0; for( int i = 0; i < n; i++ ){ if(q[i] == p[i]) x++; } return x; } #endif // DEBUG void solve(int n){ int i, j, x, p; for( i = 1; i <= n; i++ ){ available.insert(i); for( j = 1; j <= n; j++ ) candidates[i].insert(j); } std::vector<int> q(n); for( i = 1; i <= n; i++ ){ int mn = n + 1; for( j = 1; j <= n; j++ ) if( !isset[j] && candidates[j].size() < mn ){ mn = candidates[j].size(); p = j; } isset[p] = 1; while(candidates[p].size() > 1){ q[p - 1] = *candidates[p].find_by_order(genrand() % candidates[p].size()); cavailable = available; available.erase(q[p - 1]); for( j = 1; j <= n; j++ ){ if(!isset[j]){ q[j - 1] = *available.find_by_order(genrand() % available.size()); available.erase(q[j - 1]); } } available = cavailable; #ifdef PRINTQ printf("%d available : ", p); for( auto x : available ) printf("%d ", x); printf("\n"); #endif // DEBUG if( (x = query(q)) == i - 1 ){ for( j = 1; j <= n; j++ ){ if( (!isset[j] || j == p) && candidates[j].find(q[j - 1]) != candidates[j].end()) candidates[j].erase(q[j - 1]); } } else if(x == n) return; } q[p - 1] = *candidates[p].begin(); for( j = 1; j <= n; j++ ) if(!isset[j] && candidates[j].find(q[p - 1]) != candidates[j].end()) candidates[j].erase(q[p - 1]); available.erase(*candidates[p].begin()); } query(q); } #ifdef DEBUG int main(){ solve(n); int i = 0; int st = 1; for( auto x : ans ){ if(x != p[i]) st = 0; i++; } printf("Correct Permutations : %d\n", st1); printf("Good Last Permutation : %d\n", st); printf("Number Of Queries : %d\n", nq); return 0; } #endif // DEBUG

Compilation message (stderr)

mouse.cpp: In function 'void solve(int)':
mouse.cpp:75:45: warning: comparison of integer expressions of different signedness: '__gnu_pbds::detail::bin_search_tree_set<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::detail::tree_traits<int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |       if( !isset[j] && candidates[j].size() < mn ){
      |                        ~~~~~~~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...