Submission #1103347

#TimeUsernameProblemLanguageResultExecution timeMemory
1103347raduvMouse (info1cup19_mouse)C++17
Compilation error
0 ms0 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()); int bulan; static inline unsigned long long genrand(int n) { if(n == 1) return uniform_int_distribution<unsigned long long>(0, (unsigned long long)-1)(rng); return genrand(n - 1) * (unsigned long long)uniform_int_distribution<unsigned long long>(0, (unsigned long long)-1)(rng); } #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); candidates[i].erase(genrand() % n + 1); } std::vector<int> q(n); for( i = 1; i <= n; i++ ){ int mn = n + 1; p = -1; for( j = 1; j <= n / 2; j++ ) if( !isset[j] && candidates[j].size() < mn ){ mn = candidates[j].size(); p = j; } int mn1 = n + 1, p1 = -1; for( j = n / 2; j <= n; j++ ) if( !isset[j] && candidates[j].size() < mn1 ){ mn1 = candidates[j].size(); p1 = j; } if((i % 2 == 1 && p1 != -1) || p == -1) p = p1; isset[p] = 1; while(candidates[p].size() > 1){ q[p - 1] = *candidates[p].find_by_order(genrand(1) % 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(1) % 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:72:33: error: too few arguments to function 'long long unsigned int genrand(int)'
   72 |     candidates[i].erase(genrand() % n + 1);
      |                                 ^
mouse.cpp:20:34: note: declared here
   20 | static inline unsigned long long genrand(int n) {
      |                                  ^~~~~~~
mouse.cpp:79: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]
   79 |       if( !isset[j] && candidates[j].size() < mn ){
      |                        ~~~~~~~~~~~~~~~~~~~~~^~~~
mouse.cpp:85: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]
   85 |       if( !isset[j] && candidates[j].size() < mn1 ){
      |                        ~~~~~~~~~~~~~~~~~~~~~^~~~~