Submission #585015
Source Code Expand
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstdio>
using namespace std;
/// dlfcn.h ///
#ifdef __cplusplus
extern "C"{
#endif
#if defined(WIN32) || (!defined(__GNUC__) && !defined(__clang__))
void* LoadLibraryA(const char *x);
void* GetProcAddress(void *x,const char *y);
int FreeLibrary(void *x);
#elif defined(__APPLE__)
void* dlopen(const char *x,int y);
void* dlsym(void *x,const char *y);
int dlclose(void *x);
#define LoadLibraryA(s) dlopen(s,2)
#define GetProcAddress dlsym
#define FreeLibrary dlclose
#else
void* __libc_dlopen_mode(const char *x,int y);
void* __libc_dlsym(void *x,const char *y);
int __libc_dlclose(void *x);
#define LoadLibraryA(s) __libc_dlopen_mode(s,2)
#define GetProcAddress __libc_dlsym
#define FreeLibrary __libc_dlclose
#endif
#ifdef __cplusplus
}
#endif
#include "gmp.h"
typedef void (*type_mpz_init)(mpz_t);
typedef void (*type_mpz_clear)(mpz_t);
typedef void (*type_mpz_out_str)(FILE*,int,mpz_t);
typedef void (*type_mpz_set)(mpz_t,mpz_t);
typedef void (*type_mpz_set_str)(mpz_t,char*,int);
typedef void (*type_mpz_set_si)(mpz_t,long);
typedef int (*type_mpz_cmp_si)(mpz_t,long);
typedef void (*type_mpz_add)(mpz_t,mpz_t,mpz_t);
typedef void (*type_mpz_sub)(mpz_t,mpz_t,mpz_t);
typedef void (*type_mpz_mul)(mpz_t,mpz_t,mpz_t);
typedef void (*type_mpz_tdiv_q)(mpz_t,mpz_t,mpz_t);
typedef void (*type_mpz_tdiv_r)(mpz_t,mpz_t,mpz_t);
typedef void (*type_mpz_add_ui)(mpz_t,mpz_t,long);
typedef void (*type_mpz_sub_ui)(mpz_t,mpz_t,long);
typedef void (*type_mpz_mul_ui)(mpz_t,mpz_t,long);
typedef void (*type_mpz_tdiv_q_ui)(mpz_t,mpz_t,long);
typedef void (*type_mpz_tdiv_r_ui)(mpz_t,mpz_t,long);
type_mpz_init mympz_init;
type_mpz_clear mympz_clear;
type_mpz_out_str mympz_out_str;
type_mpz_set mympz_set;
type_mpz_set_str mympz_set_str;
type_mpz_set_si mympz_set_si;
type_mpz_cmp_si mympz_cmp_si;
type_mpz_add mympz_add;
type_mpz_sub mympz_sub;
type_mpz_mul mympz_mul;
type_mpz_tdiv_q mympz_tdiv_q;
type_mpz_tdiv_r mympz_tdiv_r;
type_mpz_add_ui mympz_add_ui;
type_mpz_sub_ui mympz_sub_ui;
type_mpz_mul_ui mympz_mul_ui;
type_mpz_tdiv_q_ui mympz_tdiv_q_ui;
type_mpz_tdiv_r_ui mympz_tdiv_r_ui;
int main(int argc,char **argv){
//MacPorts
//void *H=LoadLibraryA("/opt/local/lib/libgmp.dylib");
//ideone
//void *H=LoadLibraryA("/usr/lib/i386-linux-gnu/libgmp.so.10");
//paiza.io
void *H=LoadLibraryA("/usr/lib/x86_64-linux-gnu/libgmp.so.10");
//wandbox/yukicoder
//void *H=LoadLibraryA("/usr/lib64/libgmp.so.10");
mympz_init=(type_mpz_init)GetProcAddress(H,"__gmpz_init");
mympz_clear=(type_mpz_clear)GetProcAddress(H,"__gmpz_clear");
mympz_out_str=(type_mpz_out_str)GetProcAddress(H,"__gmpz_out_str");
mympz_set=(type_mpz_set)GetProcAddress(H,"__gmpz_set");
mympz_set_str=(type_mpz_set_str)GetProcAddress(H,"__gmpz_set_str");
mympz_set_si=(type_mpz_set_si)GetProcAddress(H,"__gmpz_set_si");
mympz_cmp_si=(type_mpz_cmp_si)GetProcAddress(H,"__gmpz_cmp_si");
mympz_add=(type_mpz_add)GetProcAddress(H,"__gmpz_add");
mympz_sub=(type_mpz_sub)GetProcAddress(H,"__gmpz_sub");
mympz_mul=(type_mpz_mul)GetProcAddress(H,"__gmpz_mul");
mympz_tdiv_q=(type_mpz_tdiv_q)GetProcAddress(H,"__gmpz_tdiv_q");
mympz_tdiv_r=(type_mpz_tdiv_r)GetProcAddress(H,"__gmpz_tdiv_r");
mympz_add_ui=(type_mpz_add_ui)GetProcAddress(H,"__gmpz_add_ui");
mympz_sub_ui=(type_mpz_sub_ui)GetProcAddress(H,"__gmpz_sub_ui");
mympz_mul_ui=(type_mpz_mul_ui)GetProcAddress(H,"__gmpz_mul_ui");
mympz_tdiv_q_ui=(type_mpz_tdiv_q_ui)GetProcAddress(H,"__gmpz_tdiv_q_ui");
mympz_tdiv_r_ui=(type_mpz_tdiv_r_ui)GetProcAddress(H,"__gmpz_tdiv_r_ui");
cin.tie(0);
ios::sync_with_stdio(false);
int n,a;
cin>>n>>a;
string K;
//long long K;
cin>>K;
mpz_t k;
mympz_init(k);
mympz_set_str(k,(char*)K.c_str(),10);
vector<int> b(n+1);
for(int i=1;i<=n;i++)cin>>b[i];
map<int,int>h;
int c=a;
for(int i=0;;i++){
if(h.find(b[c])!=h.end()){
int cycle=i-h[b[c]];
mympz_tdiv_r_ui(k,k,cycle);
break;
}
c=b[c];
h[c]=i;
mympz_sub_ui(k,k,1);
if(mympz_cmp_si(k,0)==0)break;
}
for(;mympz_cmp_si(k,0)>0;){
c=b[c];
mympz_sub_ui(k,k,1);
}
printf("%d\n",c);
mympz_clear(k);
FreeLibrary(H);
}
Submission Info
Submission Time |
|
Task |
D - へんてこ辞書 |
User |
leafmoon |
Language |
C++ (GCC 4.9.2) |
Score |
100 |
Code Size |
4321 Byte |
Status |
AC |
Exec Time |
48 ms |
Memory |
2100 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
All |
Score / Max Score |
0 / 0 |
50 / 50 |
50 / 50 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample_01.txt, subtask0_sample_03.txt |
Subtask1 |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_03.txt |
All |
subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask0_sample_01.txt, subtask0_sample_03.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt, subtask1_sample_02.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_0.txt |
AC |
42 ms |
1572 KB |
subtask0_1.txt |
AC |
37 ms |
1508 KB |
subtask0_2.txt |
AC |
41 ms |
1504 KB |
subtask0_3.txt |
AC |
38 ms |
1564 KB |
subtask0_4.txt |
AC |
44 ms |
1756 KB |
subtask0_5.txt |
AC |
38 ms |
1568 KB |
subtask0_6.txt |
AC |
36 ms |
1572 KB |
subtask0_7.txt |
AC |
41 ms |
1568 KB |
subtask0_8.txt |
AC |
38 ms |
1572 KB |
subtask0_9.txt |
AC |
42 ms |
1568 KB |
subtask0_sample_01.txt |
AC |
30 ms |
1248 KB |
subtask0_sample_03.txt |
AC |
28 ms |
1308 KB |
subtask1_0.txt |
AC |
42 ms |
1832 KB |
subtask1_1.txt |
AC |
43 ms |
2068 KB |
subtask1_10.txt |
AC |
48 ms |
2100 KB |
subtask1_11.txt |
AC |
31 ms |
1304 KB |
subtask1_2.txt |
AC |
40 ms |
1816 KB |
subtask1_3.txt |
AC |
42 ms |
1760 KB |
subtask1_4.txt |
AC |
43 ms |
1812 KB |
subtask1_5.txt |
AC |
46 ms |
1884 KB |
subtask1_6.txt |
AC |
42 ms |
1840 KB |
subtask1_7.txt |
AC |
40 ms |
1888 KB |
subtask1_8.txt |
AC |
47 ms |
1940 KB |
subtask1_9.txt |
AC |
47 ms |
1880 KB |
subtask1_sample_02.txt |
AC |
30 ms |
1252 KB |