Submission #1103238

#TimeUsernameProblemLanguageResultExecution timeMemory
1103238raduvMouse (info1cup19_mouse)C++17
45 / 100
3087 ms3408 KiB
#include <stdio.h> #include <stdlib.h> #include <ctime> #include <random> #include <set> #include <vector> #include <algorithm> //#define DEBUG //#define PRINTQ #ifndef DEBUG #include "grader.h" #endif // DEBUG const int MAXN = 256; std::set<int> candidates[MAXN + 1]; std::set<int> available, cavailable; bool isset[MAXN + 1]; #ifdef DEBUG int p[MAXN + 1] = {27, 83, 51, 21, 242, 154, 220, 25, 253, 125, 88, 235, 138, 161, 30, 105, 234, 36, 187, 144, 139, 98, 2, 70, 107, 122, 200, 169, 86, 74, 208, 79, 6, 130, 213, 178, 44, 164, 230, 151, 8, 180, 227, 212, 162, 191, 142, 172, 193, 166, 85, 1, 96, 136, 72, 147, 131, 56, 184, 69, 32, 11, 34, 42, 39, 190, 221, 192, 108, 41, 237, 129, 239, 61, 231, 229, 111, 177, 224, 20, 40, 251, 15, 64, 252, 210, 215, 238, 173, 250, 248, 57, 171, 246, 226, 182, 249, 14, 134, 53, 68, 133, 3, 24, 62, 114, 202, 35, 106, 127, 19, 159, 141, 179, 102, 156, 247, 117, 181, 109, 84, 233, 158, 12, 99, 153, 174, 113, 150, 95, 175, 73, 100, 149, 77, 112, 119, 176, 29, 211, 47, 7, 126, 236, 65, 4, 71, 45, 90, 80, 183, 31, 87, 137, 63, 33, 43, 94, 101, 198, 54, 232, 214, 199, 217, 75, 26, 148, 52, 38, 240, 116, 197, 110, 209, 143, 245, 219, 76, 167, 10, 49, 93, 195, 241, 17, 203, 123, 37, 120, 206, 218, 157, 50, 16, 222, 196, 89, 256, 13, 205, 244, 135, 152, 163, 58, 216, 59, 67, 23, 5, 9, 223, 81, 103, 140, 92, 28, 132, 146, 207, 78, 189, 128, 243, 145, 115, 188, 228, 18, 155, 168, 255, 48, 46, 186, 170, 185, 254, 121, 104, 55, 194, 91, 60, 66, 22, 160, 225, 82, 204, 124, 97, 201, 165, 118}; int n = 256; int nq = 0; int st1 = 1; std::vector<int> ans; #endif // DEBUG int order_of_key(std::set<int> st, int poz){ auto it = st.begin(); for( int i = 1; i <= poz; i++ ) it++; return *it; } #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)); st1 = std::min(st1, (int)isPermutation(q)); printf("\n"); #endif // PRINTQ nq++; int x = 0; for( int i = 0; i < n; i++ ){ if(q[i] == p[i]) x++; } return x; } #endif // DEBUG void solve(int n){ mt19937 mt(time(nullptr)); 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] = order_of_key(candidates[p], mt() % candidates[p].size()); cavailable = available; available.erase(q[p - 1]); for( j = 1; j <= n; j++ ){ if(!isset[j]){ q[j - 1] = order_of_key(available, mt() % 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:77:45: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |       if( !isset[j] && candidates[j].size() < mn ){
      |                        ~~~~~~~~~~~~~~~~~~~~~^~~~
mouse.cpp:110:9: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  110 |     q[p - 1] = *candidates[p].begin();
      |       ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...